poj_1273_最大流

题目描述：

  网络流的标准问题，求最大流。给出边数，点数和边容量。求最大流。

解题思路：

  最大流的算法ford_fulkerson,其中求增广路径算法edmonds_karp。两个结合求，注每次更新残留网络边容量时要添加反向的容量，校正用。

  这题的数据比较无耻，要注意重边输入需要叠加容量的问题。

代码：

#include <stdio.h>
#include <stdlib.h>
#define M 201
#define MAX 10000000

int visit[M], pre[M];
long long c[M][M];
int n, m, f;//n = edge number, m = vertex number;

void ford_fulkerson(int s, int t){
   int x, y, tmp, min;
  
   f = 0;
   while(edmonds_karp(s,t)!=0){
      //system("pause");
      //printf("ek return 1.\n");
      //find min
      min = MAX;
      x = pre[t];
      y = t;
      while(y != s){
         //printf("边[%d->%d]\t",x,y);
         if(c[x][y] < min)
            min = c[x][y];
        
         tmp = x;
         x = pre[x];
         y = tmp;
      }
      f += min;
      //printf("min=%d, f=%d\n",min, f);
      x = pre[t];
      y = t;
      while(y != s){
         c[x][y] -= min;
         c[y][x] += min;
         tmp = x;
         x = pre[x];
         y = tmp;
      }
   }
  
}

int edmonds_karp(int src, int des){
    int v, i, front, rear, que[M];
   
    memset(visit,0,sizeof(visit));
    memset(pre,0,sizeof(pre));
    front = 0;
    rear = 0;
    que[rear++] = src;
    visit[src] = 1;
    while(front!=rear){
       v = que[front++];
       for(i=1;i<=m;i++){
          if(!visit[i] && c[v][i]){
            // printf("边[%d,%d]的容量：%d\n",v,i,c[v][i]);
             que[rear++] = i;
             visit[i] = 1;
             pre[i] = v;
             if(i == des)
                return 1;
          }
       }
    }
    //printf("return 0.\n");
    return 0;
}

main()
{
   int i, x, y, w;
  
   while(scanf("%d %d",&n, &m)!=EOF){
       memset(c,0,sizeof(c));
       memset(pre,0,sizeof(pre));
       for(i=1;i<=n;i++){
          scanf("%d %d %d",&x, &y, &w);
          c[x][y] += w;
       }
       ford_fulkerson(1,m);
       printf("%d\n",f);
   }
  
   system("pause");
   return 0;
}