题目链接：click here
三种方法都用了一下，对比得出EK最少，只用46ms。
【Edmonds-Karp算法】基础的最大流算法，每次BFS寻找最短路进行增广，找出一条残余路径就可以了。然后对残余网络进行增广，不要忘记正向增广，相当于负向减少，也要在图中保存记录。最后求一个割集来得到最大流,效率O(VE2)，“找任意路径”最简单的方法是用DFS,但是数据要稍微增加就会变得较慢，采用BFS，源点和汇点保存在s和t中，净流量保存在变量f中。
代码：
/*Edmonds-Karp算法源点和汇点保持在s和t中，净流量保持在变量f中*/#include <math.h>#include <queue>#include <deque>#include <vector>#include <stack>#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>using namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);const int maxn = 20;const int inf=0x3f3f3f3f;int cap[20][20],flow[20][20];// 容量。流量int Max_flow(int t){int s=1,i,j,f=0,p[20],a[20];// p代表上一个节点，a代表残量。mem(flow,0);queue<int> Q ;while(1){while(!Q.empty())Q.pop();memset(a,0,sizeof(a));Q.push(s);a[s]=inf;while(!Q.empty()){i =Q.front();if(i==t)break;Q.pop();for(j=1; j<=t; j++){if(i!=j&&!a[j]&&cap[i][j]>flow[i][j]){p[j]=i;Q.push(j);a[j]= a[i]>cap[i][j]-flow[i][j]? cap[i][j]-flow[i][j]:a[i];}}}if(!a[t]) return f;//找不到增广路，说明此时已经是最大流了。for(i=t; i!=s; i=p[i]){flow[i][p[i]] -=a[t];flow[p[i]][i] +=a[t];}f+=a[t];}}int main(){int a,b,c,n,m,ncase,cas=1;scanf("%d",&ncase);while(ncase–){scanf("%d %d",&n,&m);memset(cap,0,sizeof(cap));while(m–){scanf("%d%d%d",&a,&b,&c);if(a==b)continue;cap[a][b]+=c;}printf("Case %d: %d\n",cas++,Max_flow(n));}return 0;}【Ford-Fulkerson】
该算法是大量算法的基础，有多种实现方法。
Ford-Fulkerson算法是一种迭代算法，首先对图中所有顶点对的流大小清零，此时的网络流大小也为0。在每次迭代中，通过寻找一条“增广路径”(augumentpath)来增加流的值。增广路径可以看作是源点s到汇点t的一条路径，并且沿着这条路径可以增加更多的流。迭代直至无法再找到增广路径位置，此时必然从源点到汇点的所有路径中都至少有一条边的满边（即边的流的大小等于边的容量大小）。
/*Ford-Fulkerson 算法 邻接表实现*/#include <ctype.h> #include <stdio.h>#include <vector>#include <stdlib.h>#include <string.h>#include <iostream>#include <algorithm>using namespace std;const int maxn = 1101;const int inf=0x3f3f3f3f;struct edge{int to,cap,rev;};vector<edge > G[maxn];//图的邻接表表示bool used[maxn];//访问标记void add_edge(int from,int to,int cap){G[from].push_back((edge){to,cap,G[to].size()});G[to].push_back((edge){from,0,G[from].size()-1});}int dfs(int v,int t,int f){if(v==t) return f;used[v]=true;for(int i=0; i<G[v].size(); i++){edge &e=G[v][i];if(!used[e.to]&&e.cap>0){int d=dfs(e.to,t,min(f,e.cap));if(d>0){e.cap-=d;G[e.to][e.rev].cap+=d;return d;}}}return 0;}int max_flow(int s,int t){int flow=0;for(;;){memset(used,0,sizeof(used));int f=dfs(s,t,inf);if(f==0) return flow;flow+=f;}}int main(){int n,m,too,capp,revv;int tt,j=1;scanf("%d",&tt);while(tt–){scanf("%d%d",&m,&n);memset(G,0,sizeof(G));for(int i=0; i<n; i++){scanf("%d%d%d",&too,&capp,&revv);add_edge(too,capp,revv);}printf("Case %d: %d\n",j++,max_flow(1,m));}return 0;}【Dinic 算法】
网络流最大流的优化算法之一，每一步对原图进行分层，然后用DFS求增广路。时间复杂度是O(n^2*m) 。
算法流程1、根据残量网络计算层次图。2、在层次图中使用DFS进行增广直到不存在增广路。3、重复以上步骤直到无法增广。/*Dinic 算法总是寻找最短路，并沿这条路增广*/#include <math.h>#include <queue>#include <deque>#include <vector>#include <stack>#include <stdio.h>#include <ctype.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <algorithm>using namespace std;#define Max(a,b) a>b?a:b#define Min(a,b) a>b?b:a#define mem(a,b) memset(a,b,sizeof(a))int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};const double eps = 1e-6;const double Pi = acos(-1.0);const int maxn = 18;const int inf=0x3f3f3f3f;struct edge{int from, to, cap;};vector<edge> EG;vector<int> G[maxn];int n, s, t, ans;int level[maxn];//顶点到源点的距离标号int cur[maxn];//当前弧，在其之前的边已经没有用了void add_edge(int from, int to, int cap){EG.push_back((edge){from, to, cap});EG.push_back((edge){to, from, 0});G[from].push_back(EG.size()-2);G[to].push_back(EG.size()-1);}bool bfs(){mem(level,-1);queue<int> que;que.push(s);level[s] = 0;while(!que.empty()){int v = que.front();que.pop();for(int i = 0; i < G[v].size(); i++){edge& e = EG[G[v][i]];if(level[e.to] == -1 && e.cap > 0){level[e.to] = level[v]+1;que.push(e.to);}}}return (level[t]!=-1);}int dfs(int v, int a){if(v == t || a == 0) return a;int flow = 0, f;for(int& i = cur[v]; i < G[v].size(); i++){edge& e = EG[G[v][i]];if(level[v]+1 == level[e.to] && (f = dfs(e.to, Min(a, e.cap))) > 0){e.cap -= f;EG[G[v][i]^1].cap += f;flow += f;a -= f;if(a == 0) break;}}return flow;}void Dinic(){ans = 0;while(bfs()){mem(cur,0);ans += dfs(s, inf);}}int main(){int T, m, from, to, cap,cas=1;scanf("%d", &T);while(T–){scanf("%d%d", &n, &m);while(m–){scanf("%d%d%d", &from, &to, &cap);add_edge(from, to, cap);}s = 1, t = n;Dinic();printf("Case %d: %d\n", cas++, ans);EG.clear();for(int i = 0; i <= n; ++i)G[i].clear();}return 0;}
，人生不如意十之八-九，与其诅咒黑暗，倒不如在生命中点燃一盏灯
