呜呜，今天自学网络流，看了EK算法，学的晕晕的，留个简单模板题来作纪念、、、
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 ", max_flow); 59 } 60 return 0; 61 }