EK.zip_Edmonds Karp_Edmonds-Karp_最大网络流_网络流

#include <iostream> #include <queue> using namespace std; const int MAXV = 810; const int MAXE = 12100; const int LIMIT = 2147483647; int g[MAXV][MAXV],f[MAXV][MAXV]; int pre[MAXV],dist[MAXV]; int v,e,ans; void init() { int i,x,y,c; memset(g,0,sizeof(g)); memset(f,0,sizeof(f)); ans = 0; for (i = 1;i <= e;i++) { cin >>x >>y >>c; g[x][y] += c; } } bool bfs() { queue<int> que; int i,j; memset(pre,-1,sizeof(pre)); que.push(1); dist[1] = LIMIT; pre[1] = 1; while (!que.empty()) { i = que.front(); que.pop(); for (j = 1;j <= v;j++) { if (pre[j] == -1 && g[i][j] > f[i][j]) { dist[j] = dist[i] < g[i][j] - f[i][j]; pre[j] = i; if (j == v) return true; que.push(j); } } } return false; } void work() { int i; while (bfs()) { for (i = v;i != 1; i = pre[i]) { f[pre[i]][i] += dist[v]; f[i][pre[i]] = -f[pre[i]][i]; } ans += dist[v]; } } void out() { cout <<ans <<endl; } int main() { while (cin >>e >>v) { init(); work(); out(); } return 0; }