前言

粗略地讲一下吧，大概能理解就行

理论部分借鉴了 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;
	}
};

实现用的链式前向星建图，比较方便。