前言
粗略地讲一下吧，大概能理解就行
理论部分借鉴了 oi-wiki ，有问题欢迎指出
网络流
网络是一个特殊有向图 $G=(V,E)$ ，特殊在于有源点 $s$ 和汇点 $t$
首先网络流图中每条边 $(u,v)$ 都有一个容量 $c(u,v)$
介绍流函数 $f(u,v)$ ，指 $u$ 到 $v$ 流量
所以就会有流量守恒，即 $0 \leq f(u,v) \leq c(u,v)$
然后一个点的净流量是指 $u$ 向其它点的流量减去其它点向它的流量
所以有净流量 $f(u)=\sum_{x\in V} f(u,x) - \sum_{x\in V} f(x,u) $
而图 $G$ 的流量就是 $|f(s)|$
最大流
就是求 $|f(s)|$ 的最大值
思路和二分图很像，就是一直找 $s$ 到 $t$ 的增广路
直到不存在增广路为止，于是就诞生了 EK(Edmond-Karp) 算法
复杂度证明比较复杂，就不讨论了，复杂度是 $O(n m^2)$ ，但跑不满， $1000$ 的数据跑着也比较轻松（
但这里主要介绍代码长度与 EK 差不多 ，复杂度更为优秀的 Dinic 算法
Dinic算法
发现 EK 可能会把很多拓展过后的点或边再拓展
我们在每次有效增广过后删除增广的边
并且用 $bfs$ 先建立分层图，保证沿着搜索顺序扩张
复杂度 $O(n^2m)$
代码：
template<int T> struct Dinic{
struct edge{
int v,w,next;
}e[T*5+5];
int head[T+5],tot,now[T+5],d[T+5];
Dinic(){
tot=1;
for(int i=1;i<=T;i++) head[i]=0;
}
inline void add(int x,int y,int c){
e[++tot]={y,c,head[x]};
head[x]=tot;
e[++tot]={x,0,head[y]};
head[y]=tot;
}
int inf=2e9;
inline int bfs(int s,int t){
for(int i=1;i<=T;i++) d[i]=0;
queue<int> q;
while(q.size()) q.pop();
d[s]=1; q.push(s); now[s]=head[s];
while(q.size()){
int u=q.front();
q.pop();
for(int i=now[u];i;i=e[i].next){
int v=e[i].v;
if(e[i].w&&d[v]==0){
d[v]=d[u]+1;
now[v]=head[v];
q.push(v);
if(v==t) return 1;
}
}
}
return 0;
}
int dinic(int u,int flow,int t){
if(u==t) return flow;
int rest=flow,ret=0;
for(int i=now[u];i&&rest;i=e[i].next){
int v=e[i].v;
now[u]=i;
if(e[i].w&&(d[v]==d[u]+1)){
int p=dinic(v,min(rest,e[i].w),t);
if(!p){
d[v]=0;
continue;
}
rest-=p;
ret+=p;
e[i].w-=p;
e[i^1].w+=p;
}
}
return ret;
}
inline int flow(int s,int t){
for(int i=1;i<=T;i++) now[i]=0;
int ret=0,w;
while(bfs(s,t)) {
while(1){
w=dinic(s,inf,t);
ret+=w;
if(!w) break;
}
}
return ret;
}
};
实现用的链式前向星建图，比较方便。