1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 #include<set> 6 #include<algorithm> 7 #define CLR(a,b) memset((a),(b),sizeof((a))) 8 using namespace std; 9 10 const int N = 201;11 const int inf = 0x3f3f3f3f;12 int n, m;13 int g[N][N];//i到j的容量14 int pre[N];//i的前驱节点15 bool vis[N];16 int flow[N][N];//从i到j的流量17 int a[N];//从源点到i节点的最小残留量18 19 int Edmonds_Karp(int st, int ed){20     int u, v;21     int f = 0;//最大流22     queue<int>q;//bfs找增广路23     while(1){24         CLR(vis, 0); CLR(a, 0);//每找一次记得初始化25         q.push(st);26         vis[st] = 1;27         a[st] = inf;28         while(!q.empty()){29             u = q.front(); q.pop();30             for(v = 1; v <= n; ++v){31                 if(!vis[v] && g[u][v] > flow[u][v]){32                     q.push(v);33                     pre[v] = u;34                     vis[v] = 1;35                     a[v] = min(a[u], g[u][v] - flow[u][v]);36                 }37             }38         }39         if(a[ed] == 0) break;//当前已经是最大流40         f += a[ed];41         for(u = ed; u != st; u = pre[u]){42             flow[pre[u]][u] += a[ed];43             flow[u][pre[u]] -= a[ed];44         }45 46     }47     return f;48 }49 int main(){50     int i, j, k, a, b, c;51     while(scanf("%d %d", &m, &n)==2){52         CLR(g, 0); CLR(flow, 0);53         for(i = 0; i < m; ++i){54             scanf("%d %d %d", &a, &b, &c);55             g[a][b] += c;//可能有重边56         }57         int max_flow = Edmonds_Karp(1, n);58         printf("%d\n", max_flow);59     }60     return 0;61 }