模板题
这三种算法基于寻找增广路径来求解最大流，当一个网络图中不存在增广路径时我们就得到了最大流；
1.EK:
//直接使用bfs找最近的增广路径，每找到一条就更新残余网络，然后继续找，直到不存在为止，这个真好懂^ V ^
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
const int maxn = 10000+10;
const int maxm = 100000 + 10;
const int inf_max = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
int n,m,head[maxn],cnt,flow[maxn];
struct EDG {int w,v,nxt,id;EDG() {}EDG(int tv,int tw,int tn) {w=tw,v=tv,nxt=tn;}
}edge[maxm<<1],pre[maxn];
void Initial() {memset(head,-1,sizeof(head));cnt = 0;
}
void add_edge(int u,int v,int w) {edge[cnt] = EDG(v,w,head[u]);head[u] = cnt++;
}
int bfs(int s,int e) {for(int i = 1;i <= n; ++i) pre[i].v = -1,flow[i] = 0;flow[s] = inf_max;queue<int>q;while(!q.empty()) q.pop();q.push(s);while(!q.empty()) {int u = q.front();q.pop();// printf("u:%d %d\n",u,q.size());if(u == e) return flow[e];for(int i = head[u]; ~i; i= edge[i].nxt) {int v = edge[i].v,w = edge[i].w;if(w && pre[v].v == -1) {flow[v] = min(w,flow[u]);q.push(v);pre[v].v = u;pre[v].id = i;}}}return -1;
}
int Maxflow(int s,int e) {int addflow,ret = 0;while((addflow = bfs(s,e)) != -1) {ret += addflow;//cout<<addflow<<endl;int k = e;while(k != s) {edge[pre[k].id].w -= addflow;edge[pre[k].id^1].w += addflow;k = pre[k].v;}}return ret;
}
int main()
{int s,e;scanf("%d%d%d%d",&n,&m,&s,&e);Initial();for(int i = 1;i <= m; ++i) {int u,v,w;scanf("%d%d%d",&u,&v,&w);if(u == v) continue;add_edge(u,v,w),add_edge(v,u,0);}cout<<Maxflow(s,e)<<endl;return 0;
}
2.sap(未优化)
//不是很懂，反正就是赋予了每个点一个距离汇点的距离标号d[i]，用来标识某点的汇点的所有路径中弧的最短数量（权值为1的最短路嘛），同时对于弧<u,v>，若d[u] = d[v] + 1，则称弧<u,v>为允许弧。找增广路径的时候只能走允许弧。这样保证走的一定是最短路。同时回溯的时候，更新我们的距离标号，直到出现断层；
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
const int maxn = 10000+10;
const int maxm = 100000 + 10;
const int inf_max = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
//最大流：EK,sap,dinic
int n,m,head[maxn],cnt,num[maxn],h[maxn],s,e;
struct EDG{int v,w,nxt;EDG() {}EDG(int tv,int tw,int tn) {v=tv,w=tw,nxt=tn;}
}edge[maxm << 1];
void Initial() {memset(head,-1,sizeof(head));memset(h,0,sizeof(h));cnt = 0;
}
void add_edge(int u,int v,int w) {edge[cnt] = EDG(v,w,head[u]);head[u] = cnt++;
}
int dfs(int now,int flow) {int sum = 0;if(now == e) return flow;for(int i = head[now]; ~i;i = edge[i].nxt) {int v = edge[i].v,w = edge[i].w;if(w && h[now] == h[v] + 1) {int tmp = dfs(v,min(flow-sum,w));edge[i].w -= tmp;edge[i^1].w += tmp;sum += tmp;if(flow == sum) return sum;}}if(h[s] >= n) return sum;num[h[now]]--;if(num[h[now]] == 0) h[s] = n;h[now]++;num[h[now]]++;return sum;
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&e);Initial();for(int i = 1;i <= m; ++i) {int u,v,w;scanf("%d%d%d",&u,&v,&w);if(u == v) continue;add_edge(u,v,w);add_edge(v,u,0);}num[0] = n;int ans = 0;while(h[s] < n) {ans += dfs(s,inf_max);}cout<<ans<<endl;return 0;
}
3.dinic
//这个就是sap算法中回溯更新点的过程搞了一个单独的BFS来执行;然后这个每次的BFS更新距离标号数组(emm，和sap的差不多，只是这个是到源点的)，使得原图成为了一个层次图，然后在层次图中用dfs寻找增广路。
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<map>
#include<cstring>
#include<queue>
const int maxn = 10000+10;
const int maxm = 100000 + 10;
const int inf_max = 0x3f3f3f3f;
using namespace std;
typedef long long ll;
//Dinic
int n,m,s,e,head[maxn],cnt,h[maxn];
struct EDG{int v,w,nxt;EDG() {}EDG(int tv,int tw,int tn) {v=tv,w=tw,nxt=tn;}
}edge[maxm<<1];
void Initial() {cnt = 0;memset(head,-1,sizeof(head));
}
void add_edge(int u,int v,int w) {edge[cnt] = EDG(v,w,head[u]);head[u] = cnt++;
}
bool bfs(int now) {memset(h,-1,sizeof(h));h[now] = 0;queue<int>q;while(!q.empty()) q.pop();q.push(now);while(!q.empty()) {int u = q.front();q.pop();if(u == e) return true;for(int i = head[u];~i;i = edge[i].nxt) {int v = edge[i].v,w = edge[i].w;if(w && h[v] == -1) {h[v] = h[u] + 1;q.push(v);}}}return false;
}
int dfs(int now,int flow) { //now表示当前点，flow表示流入当前点的流量，返回实际流入当前点的流量，即增广路径的流量if(now == e) return flow;int sum = 0;for(int i = head[now]; ~i ; i =edge[i].nxt) {int v = edge[i].v,w = edge[i].w;if(w && h[v] == h[now] + 1) { //如果可能形成增广路径int tmp = dfs(v,min(flow - sum,w));sum += tmp;edge[i].w -= tmp;edge[i^1].w += tmp;}}return sum;
}
int main()
{scanf("%d%d%d%d",&n,&m,&s,&e);Initial();for(int i = 1;i <= m;++i) {int u,v,w;scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w);add_edge(v,u,0);}int maxflow = 0;while(bfs(s)) {maxflow += dfs(s,e);}cout<<maxflow<<endl;return 0;
}