/* Time：2015-6-18 接触网络流好几天了 写的第一个模版————Ford-Fulkerson算法 作用：求解网络最大流 注意：源点是0 汇点是1 如果题目输入的是1到n 请预处理减1 */ #include<cstdio> #include<cstring> #include<cmath> #include<queue> #include<algorithm> using namespace std; const int INF = 0x7fffffff;//无穷大 const int maxn = 1000 + 10;//这里可以设置结点的数量 int n, m; int flag[maxn], pre[maxn], alpha[maxn]; int c[maxn][maxn], f[maxn][maxn]; queue<int>Q; int main() { int i, j, u, v, cc, ff; scanf("%d%d", &n, &m); for (i = 0; i<n; i++) for (j = 0; j<n; j++) c[i][j] = INF, f[i][j] = INF; //初始化不存在弧 for (i = 0; i<m; i++) { scanf("%d%d%d%d", &u, &v, &cc, &ff);//输入弧的起点，弧的终点，弧的容量，弧的流量 //解决重边问题 if (c[u][v] == INF) { c[u][v] = cc; f[u][v] = ff; } else { c[u][v] += cc; f[u][v] += ff; } } //0是源点 n-1汇点 int startt, endd; startt = 0; endd = n - 1; while (1) { while (!Q.empty()) Q.pop(); memset(flag, -1, sizeof(flag)); memset(pre, -1, sizeof(pre)); memset(alpha, -1, sizeof(alpha)); flag[startt] = 0;//源点已标号 但是未检查邻接顶点 pre[startt] = 0;//源点从自己推过来 alpha[startt] = INF;//源点可以发出INF的流量 Q.push(startt); while ((!Q.empty()) && flag[endd] == -1) { int h = Q.front(); Q.pop(); for (i = 0; i<n; i++) { //前向弧 if (c[h][i] != INF)//有路 { if (f[h][i]<c[h][i])//不饱和 { if (flag[i] == -1)//i顶点未标号 { flag[i] = 0;//i顶点已标号 但是未检查邻接顶点 pre[i] = h;//i从h推过来 //alpha[i]取决于alpha[h]与c[h][i]-f[h][i]的较小值 if (c[h][i] - f[h][i] <= alpha[h]) alpha[i] = c[h][i] - f[h][i]; else alpha[i] = alpha[h]; Q.push(i);//i顶点进入队列 等待检查邻接顶点 } } } //后向弧 if (c[i][h] != INF)//有路 { if (f[i][h]>0)//非零流弧 { if (flag[i] == -1)//i顶点未标号 { flag[i] = 0;//i顶点已标号 但是未检查邻接顶点 pre[i] = -h;//i从h推过来 标号为- 意思是后向弧 //alpha[i]取决于alpha[h]与f[i][h]的较小值 if (alpha[h] <= f[i][h]) alpha[i] = alpha[h]; else alpha[i] = f[i][h]; Q.push(i);//i顶点进入队列 等待检查邻接顶点 } } } } flag[h] = 1;//h顶点已标号，并且已经检查所有的邻接顶点 } if (flag[endd] == -1 || alpha[endd] == 0) break; //已经不存在增广路，不再寻找 int a = alpha[endd];//可改进量 int now = endd; while (1) { if (now == 0) break; if (pre[now] >= 0) { f[pre[now]][now] += a; now = pre[now]; } else if (pre[now]<0) { f[now][-pre[now]] -= a; now = -pre[now]; } } } for (i = 0; i<n; i++) for (j = 0; j<n; j++) if (f[i][j] != INF) printf("%d --> %d : %d ", i, j, f[i][j]); int maxflow = 0; for (i = 0; i<n; i++) if (f[0][i] != INF) maxflow += f[0][i]; printf("maxflow = %d ", maxflow); return 0; }