感觉网络流已经废了。。勉强背背dinic板子
关于dinic的想法其实来自于一个简易的最大流，每次找到一条增广路然后dfs跑一次，即一次bfs一次dfs一条路。
可是我们bfs跑出的分层图很可能会跑出多条增广路，于是我们dfs的时候将所有可能的增广路跑完。
关于当前弧优化，即我们每次边在跑dfs的时候如果已经将一条路榨干，那么在该分层图跑下一次dfs的时候就可以跳过这条路。具体做法我们建完分层图用cur[]复制原本的head[]数组，然后在cur上跑，cur榨干一条路即更改值到下一条路，于是就不会再重复浏览该路。
还有一个小优化不知道有没有用，就是发现一个点一滴水都不能增广则直接将该点从分层图中去除。
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e4+5;
int N,M;
int en[maxn],nt[maxn],la[maxn],cla[maxn],owo=1,len[maxn];
void adg(int x,int y,int z) {
en[++owo] = y; nt[owo]=cla[x]; cla[x]=owo; len[owo]=z;
en[++owo] = x; nt[owo]=cla[y]; cla[y]=owo; len[owo]=0;
}
int qe[maxn],qf,qm,dis[maxn];
bool bfs() {
qf = qm = 1; qe[1] = 1; dis[1] = 0;
for(int i=2;i<=M;i++) dis[i] = -1;
while(qf<=qm) {
int x = qe[qf++];
for(int it=cla[x];it;it=nt[it]) {
int y = en[it];
if(dis[y]==-1&&len[it]>0) {
dis[y] = dis[x] + 1;
qe[++qm] = y;
}
}
}
return dis[M]!=-1;
}
int dfs(int x,int flow) {
if(x==M) return flow;
int re = 0;
for(int &it=la[x];it;it=nt[it]) {
int y = en[it];
if(dis[y]==dis[x]+1&&len[it]>0) {
int ff = dfs(y,min(len[it],flow));
flow -= ff; re += ff;
len[it] -= ff; len[it^1] += ff;
if(!flow) break;
}
}
if(!re) dis[x] = -1;
return re;
}
int main(){
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
adg(x,y,z);
}
int ans = 0;
//dinic
while(bfs()) {
for(int i=1;i<=M;i++) la[i] = cla[i];
ans += dfs(1,0x3f3f3f3f);
}
printf("%d",ans);
return 0;
}
【MOBAN】网络流之最大流dinic的模板luoguP2740草地排水
原文：https://www.cnblogs.com/newuser233/p/15306693.html