网络流_1273.txt

推荐pku上的好题

//网络流的好题，推荐大家共享
该算法要用到 Dijkstra 算法。
每次用Dijkstra算法求的一条可通过的路后，找出该路上面的最小的权值 MIN，然后将该路径上的每条边的权值 减去 MIN ，反方向的权值加 MIN （ 例如：e( v1, v2 ) 是路径上面的一条边，则Map[v1][v2] -= MIN, Map[v2][v1] += MIN ). 累计MIN， 其最后的值就是所要求的最大流。
当最后 在图中找不到连接 1, n 两点的路径时，算法完毕。
#include <stdio.h>
#include <string.h>
#define maxn 250
struct Map
{
 int f;
 int c;
}map[maxn][maxn];
int pre[maxn];
int q[maxn*maxn];
int v[maxn];
int N,M;
int s,t;
int abs( int x ){ return x > 0 ? x : -x ; }
int min( int x, int y ){ return  x < y ? x : y; }
void init()
{
 int i, S, E, C;
 memset( map, 0, sizeof(map) );
 for(i=0;i<N;i++)
 {
  scanf( "%d%d%d", &S, &E, &C );
  map[S][E].c += C;
 } 
}
void solve()
{
 int i,j;
 int head,tail;
 s = 1;
 t = M;
 while(true)
 {
  memset( pre, 0, sizeof(pre) );
  head = 0, tail = 1;
  q[0] = s;
  v[s] = 1000000000;
  pre[s] = s;
  while( head < tail && pre[t] == 0 )
  {
   i = q[head];
   for( j = 1; j <= M; j++ )
   {
    if( pre[j] == 0 )
    {
     if( map[i][j].f < map[i][j].c )
      pre[j] = i , q[tail++] = j , v[j] = min( v[i], map[i][j].c-map[i][j].f );
     else if( map[j][i].f > 0 )
      pre[j] = -i, q[tail++] = j , v[j] = min( v[i], map[j][i].f );
    }
            }
   head++;
  }
  if( pre[t] == 0 )break;

  i = t;
  while( i != s )
  {
   j = abs( pre[i] );
   if( pre[i] > 0 )map[j][i].f += v[t];
   else map[i][j].f -= v[t];
   i = j;
  }
 }
 int ans = 0;
 for( i = 1; i <= M; i++ )ans += map[s][i].f;
 printf("%d\n",ans);
}
int main()
{
 while(scanf("%d%d",&N,&M)!=EOF)
 {
  init();
  solve();
 }
 return 0;
}