用的是EdmondsKarp
程序可以再优化的,懒得优化了
EdmondsKarp
#include <iostream> #include<stdio.h> #include <queue> #include <limits> #include <cstring> using namespace std; const int maxNode = 202; int N = 201;//edge int M = 201;//node const int maxInt = numeric_limits<int>::max(); int g[maxNode][maxNode]; int f[maxNode][maxNode]; int residual[maxNode][maxNode]; int pre[maxNode]; bool BFS() { queue<int> q; q.push(1); memset(pre,0,sizeof(int)*(M+1)); int used[maxNode]; memset(used,0,sizeof(int)*(M+1)); used[1] = 1; while (!q.empty()) { int curr = q.front(); q.pop(); for (int i=1;i<=M;++i) { if(residual[curr][i]>0 && !used[i]) { pre[i] = curr; if(i==M) return true; q.push(i); used[i] = 1; } } } return false; } void EdmondsKarp() { while (BFS()) { int minF = maxInt; int curr = M; int beg=0,end = 0; while (curr!=1) { int preNode = pre[curr]; if(minF > residual[preNode][curr]) { minF = residual[preNode][curr]; beg = preNode; end = curr; } curr = preNode; } curr = M; while (curr != 1) { int preNode = pre[curr]; f[preNode][curr] +=minF; residual[preNode][curr] -=minF; residual[curr][preNode] = f[preNode][curr]; curr = preNode; } } int sum=0; for (int i=1;i<M;++i) { sum +=f[i][M]; } cout<< sum<<endl; } int main() { while(scanf("%d%d",&N,&M)!=EOF) { for (int i=1;i<=M;++i) { memset(g[i],0,sizeof(int)*(M+1)); memset(f[i],0,sizeof(int)*(M+1)); memset(residual[i],0,sizeof(int)*(M+1)); } for (int i=0;i<N;++i) { int start,end,capacity; scanf("%d%d%d",&start,&end,&capacity); g[start][end] += capacity;//这个地方太坑爹了,不是最大的容量吗,为毛要加呢 residual[start][end] += capacity; } /*for (int i=1;i<=M;++i) { for(int j=1;j<=M;++j) cout<<g[i][j]<<" "; cout<<endl; }*/ EdmondsKarp(); } return 0; }
下面是别人优化的比较好的
#include<iostream> #include<cstring> #include<queue> using namespace std; #define inf INT_MAX int n,m,a[205][205],pre[205]; int bfs() { queue<int>Q; Q.push(1); pre[1]=0; memset(pre,-1,sizeof(pre)); int t,i; while(!Q.empty()) { t=Q.front(); Q.pop(); for(i=2;i<=n;i++) if(pre[i]==-1&&a[t][i]>0) { pre[i]=t; Q.push(i); if(i==n) return 1; } } return -1; } int maxflow() { int res=0,ans,t; while(bfs()==1) { t=n; ans=inf; while(t!=1) { if(a[pre[t]][t]<ans) ans=a[pre[t]][t]; t=pre[t]; } res=res+ans; t=n; while(t!=1) { a[pre[t]][t]-=ans; a[t][pre[t]]+=ans; t=pre[t]; } } return res; } int main() { while(scanf("%d%d",&m,&n)!=EOF) { int i,j; memset(a,0,sizeof(a)); for(i=0;i<m;i++) { int b,c,d; scanf("%d%d%d",&b,&c,&d); a[b][c]+=d; } printf("%d\n",maxflow()); } }
最大流效率更高的算法为:
Push-Relabel算法
Relabel-to-Front算法(http://cuitianyi.com/blog/%E6%B1%82%E6%9C%80%E5%A4%A7%E6%B5%81%E7%9A%84relabel-to-front%E7%AE%97%E6%B3%95/)
Preflow-Push算法
Dinic算法(可以参考国家集训队 2007 王欣上《浅谈基于分层思想的网络流算法》)