重修 网络最大流（即最小割）
本蒟蒻只讲一些我常常出错的部分，具体还要靠 OI-wiki:Dinic 的帮助。
啥是最大流？
相当于有一个供水站，一个用户，中间有复杂的水管（每一根单向且有单位时间传输量限制）网络，求用户单位时间内获得的最大水量。
Dinic 咋弄？
每次先 BFS 按照离原点 \(S\) 的距离将图分层，再在分层图上 DFS，终止条件为 BFS 时候汇点 \(T\) 与 \(S\) 不连通。DFS 时每次找一条通的管道注水，当然一次 DFS 整体看起来像打通了一棵树（多路增广）。
如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边（当前弧优化）。
时间？
\(O(n^2m)\)（前提是加上多路增广和当前弧优化）(事实上在一般的网络上，Dinic 算法往往达不到这个上界。)
特别地，在求解二分图最大匹配问题时，Dinic 算法的时间复杂度是 \(O(m\sqrt{n})\)。
建议？
建议一遍写对，难调的很 qwq。
我的代码？
Luogu 模板题:
//Said no more counting dollars. We'll be counting stars.
#include
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define int long long
#define N 210
#define M 5010
const int inf=1e14;
int n,m,s,t;
struct node{int to,nxt,res;}e[2*M];//res:残量 有反向边，空间开两倍
int head[N],cur[N],tot=1;//cur:当前到的前向星（当前弧优化） tot=1:方便 xor 1 取反向边
inline void adde(int x,int y,int z){
e[++tot]={y,head[x],z}; head[x]=tot;
e[++tot]={x,head[y],0}; head[y]=tot;//反向边 init 0
}
queue q;
int dep[N];//分层
bool bfs(){
For(i,1,n) dep[i]=0;//分层图
dep[s]=1;
while(!q.empty()) q.pop();
q.push(s);
int x;
while(!q.empty()){
x=q.front();
q.pop();
cur[x]=head[x];//init 当前到的前向星
for(int i=head[x],to;i;i=e[i].nxt){
to=e[i].to;
if(!e[i].res || dep[to]) continue;
dep[to]=dep[x]+1;
q.push(to);
}
}
return dep[t];//返回是否连通
}
int dfs(int x,int flow){
if(x==t) return flow;//送达
int ans=0,tmp,to;
for(int& i=cur[x];i;i=e[i].nxt){//传实参，cur[x]随之改变
to=e[i].to;
if(!e[i].res || dep[to]!=dep[x]+1) continue; //要有空间增广 & 要按照分层图增广
tmp=dfs(to,min(flow,e[i].res));
e[i].res-=tmp;
e[i^1].res+=tmp;
ans+=tmp;
flow-=tmp;
if(!flow) break;//已经结束咧！
}
return ans;
}
signed main(){IOS;
cin>>n>>m>>s>>t;
int x,y,z;
while(m--){
cin>>x>>y>>z;
adde(x,y,z);
}
int ans=0;
while(bfs()) ans+=dfs(s,inf);
cout< 最小点割（要拆点）原题：
//Said no more counting dollars. We'll be counting stars.
#pragma GCC optimize(2,3)//For Web Contests
#include
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define pb emplace_back
#define For(i,j,k) for(int i=j;i<=k;i++)
#define Rof(i,j,k) for(int i=j;i>=k;i--)
#define int long long
#define N 220
#define endl '\n'
const int inf=1e12;
struct node{int to,c,nxt;}e[N*N];
int head[N],cur[N],tot=1,n,m,s,t,dep[N],col[N];
inline void adde(int x,int y,int c){
e[++tot]={y,c,head[x]};head[x]=tot;
e[++tot]={x,0,head[y]};head[y]=tot;
}
queue q;
bool bfs(){
For(i,1,2*n+2) dep[i]=0;
dep[s]=1;
while(!q.empty()) q.pop();
q.push(s);
int x;
while(!q.empty()){
x=q.front();
cur[x]=head[x];
q.pop();
for(int i=head[x];i;i=e[i].nxt){
if(!e[i].c || dep[e[i].to]) continue;
dep[e[i].to]=dep[x]+1;
q.push(e[i].to);
}
}
return dep[t];
}
int dfs(int rt,int flow){
if(rt==t) return flow;
int res=0,tmp;
for(int &i=cur[rt];i;i=e[i].nxt){//当前弧优化&多路增广
if(!e[i].c || dep[e[i].to]!=1+dep[rt]) continue;
tmp=dfs(e[i].to,min(flow,e[i].c));
e[i].c-=tmp;
e[i^1].c+=tmp;
flow-=tmp;
res+=tmp;
if(!flow) break;
}
return res;
}
int dinic(){
int res=0;
while(bfs()) res+=dfs(s,inf);
return res;
}
void color(int rt){
col[rt]=1;
for(int i=head[rt];i;i=e[i].nxt){
if(!e[i].c || col[e[i].to]) continue;
color(e[i].to);
}
}
signed main(){IOS;
cin>>n>>m;
int x,y;
while(m--){
cin>>x>>y;
adde(x,y+n,inf);
adde(y,x+n,inf);
}
For(i,1,n){
cin>>x;
if(i==1 || i==n) x=inf;
adde(i+n,i,x);
}
s=n*2+1,t=n*2+2;
adde(s,1,inf);
adde(n*2,t,inf);
cout< ans;
For(i,2,n-1)
if(col[i]!=col[i+n])
ans.pb(i);
cout<