Poj 1273 Drainage Ditches(最大流 Edmonds-Karp )

题目链接：poj1273 Drainage Ditches

呜呜，今天自学网络流，看了EK算法，学的晕晕的，留个简单模板题来作纪念、、、

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<cstring>

 #include<set>

 #include<algorithm>

 #define CLR(a,b) memset((a),(b),sizeof((a)))

 using namespace std;

 const int N = ;

 const int inf = 0x3f3f3f3f;

 int n, m;

 int g[N][N];//i到j的容量

 int pre[N];//i的前驱节点

 bool vis[N];

 int flow[N][N];//从i到j的流量

 int a[N];//从源点到i节点的最小残留量

 int Edmonds_Karp(int st, int ed){

     int u, v;

     int f = ;//最大流

     queue<int>q;//bfs找增广路

     while(){

         CLR(vis, ); CLR(a, );//每找一次记得初始化

         q.push(st);

         vis[st] = ;

         a[st] = inf;

         while(!q.empty()){

             u = q.front(); q.pop();

             for(v = ; v <= n; ++v){

                 if(!vis[v] && g[u][v] > flow[u][v]){

                     q.push(v);

                     pre[v] = u;

                     vis[v] = ;

                     a[v] = min(a[u], g[u][v] - flow[u][v]);

                 }

             }

         }

         if(a[ed] == ) break;//当前已经是最大流

         f += a[ed];

         for(u = ed; u != st; u = pre[u]){

             flow[pre[u]][u] += a[ed];

             flow[u][pre[u]] -= a[ed];

         }

     }

     return f;

 }

 int main(){

     int i, j, k, a, b, c;

     while(scanf("%d %d", &m, &n)==){

         CLR(g, ); CLR(flow, );

         for(i = ; i < m; ++i){

             scanf("%d %d %d", &a, &b, &c);

             g[a][b] += c;//可能有重边

         }

         int max_flow = Edmonds_Karp(, n);

         printf("%d\n", max_flow);

     }

     return ;

 }