网络流初步——最大流

一、基础定义

网络 ：一个网络G=(V,E)是一张有向图；
容量 ：图中每条边(u,v)∈E都有一个给定的权值c(u,v)被称为容量
源/汇点：两个指定的特殊节点,分别设为S/T
流函数/流量/剩余容量 ：设f(x,y)中x、y均为图上节点，且满足：

• f(x,y)<=c(x,y)
• f(x,y)=-f(y,x)
• 对于除源/汇点外的任意节点，∑f(u,x)=∑f(x,v)( (u,x),(x,v)∈E )

则称f(x,y)为网络的 流函数 。对于(x,y)∈E，f(x,y)被称为边的 流量，c(x,y)-f(x,y)被称为边的 剩余容量 。网络中由源点出发的每条路径的流量总和被称为被称为 整个网络的流量

流函数性质： 上述三条性质，分别被称为 容量限制 ，斜对称 与 流量守恒 。尤其是流量守恒定律，它告诉我们网络中除源汇点之外，所有节点都不存储流，流出总量等于流入总量，就像“流”从源点源源不断地产生，在不超过容量限制的前提下不断地流经整个网络，最终全部进入汇点。

注意：每一条边的反向边都有一个负的流量

---

二、最大流

1.定义： 使得某一张网络的流量最大的流函数被称为最大流，此时网络的流量被称为 最大流量
2.算法： 种类很多，下面主要介绍Edmonds_Karp增广路算法 与 Dinic算法

Edmonds_Karp增广路算法

主要思想： 若存在一条路径，其最小剩余容量不为0,则称该路径为增广路。EK算法就是通过BFS不断找到增广路，直到网络中不再有增广路。显然，此时的流函数就是最大流。
流程：
在每轮寻找增广路时，EK算法仅考虑剩余容量不为0的边，找到任意一条由S到T的路径，该条路径上的最小剩余容量（设为minf)就是网络可以增加的流量
需要注意的是，当一条边的流量增加时，根据斜对称性质，其反向边流量f(y,x)<0，此时必有f(y,x)<c(y,x)。故EK算法还需要考虑每条边的反向边。
具体实现时，可以利用“成对存储”的技巧，边权的定义可以直接规定为剩余容量``。
复杂度： O(nm² ),实际上远远达不到这个上界。
一般能处理10³ ~10⁴ 级别的网络流

---

Dinic算法

在任意时刻，网络中所有点以及剩余容量大于0的边构成的子图被称为 残量网络。
S到任意点的最短距离被称为这个节点的层次，在残量网络中，满足d[y]=d[x]+1的边(x,y)构成的子图被称为分层图。分层图显然是DAG。
Dinic算法不断重复以下步骤，直到在残量网络中S不能到达T:

• 1.在残量网络上BFS求出节点的层次，构造分层图；
• 2.在分层图上dfs寻找增广路，在回溯时实时更新剩余容量

洛谷P3376

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
typedef long long LL;
il int read()
{
	int s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){ s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
}
il LL read_ll()
{
	LL s=0,w=1;char c=getchar();
	while(c<'0'||c>'9'){ if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9'){ s=(s<<1)+(s<<3)+c-'0';c=getchar();}
	return s*w;
}
const int N=210;
const int M=1e4+10;
const LL MAX=1<<29;
int n,m,S,T;
LL maxflow;
int head[N],ver[M],nxt[M],d[N],tot;
LL quan[M];
queue<int>q;
il void kkk(int u,int v,LL w){
	ver[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
	quan[tot]=w;//边权的意义为“剩余容量” 
}
il bool bfs()
{//在残量网络中构建分层图 
	memset(d,0,sizeof(d));
	while(!q.empty()) q.pop();
	q.push(S);d[S]=1;
	while(!q.empty()){
		int xx=q.front();q.pop();
		for(re int i=head[xx];i;i=nxt[i]){
			if(quan[i] && (!d[ver[i]])){
				q.push(ver[i]);
				d[ver[i]]=d[xx]+1; 
				if(ver[i]==T) return 1;
				//如果残量网络中还能找到增广路返回1 
			}
		}
	}return 0;
}
il LL dfs_di(int x,LL flow)
{//flow表示从S到x的路径上最小剩余容量 
	if(x==T) return flow;//找到minf(最小剩余容量) 
	LL rest=flow,k=0;
	//rest记录当前路径(S,x)上最小剩余容量
	//k记录路径(x,T)上剩余容量的减少量
	//根据流量守恒，(S,x)上的流量也要相应减少 
	for(re int i=head[x];i && rest;i=nxt[i]){
		//注意弹出条件，只要路径上有一条边的剩余容量
		//变为0，那么就直接返回 
		if(quan[i] && d[ver[i]]==d[x]+1){
			k=dfs_di(ver[i],min(rest,quan[i]) );
			//是rest 不是flow!(出过错) 
			if(!k) d[ver[i]]=0;
			//剪枝，如果任意(x,T)都不是增广路，将x去掉 
			quan[i]-=k;
			quan[i^1]+=k;//“成对存储”技巧
			rest-=k; 
		}
	}
	return flow-rest;
}
il void dinic()
{
	LL flow=0;
	while(bfs())
		while(flow=dfs_di(S,MAX)) maxflow+=flow;
}
int main()
{
	n=read(),m=read(),S=read(),T=read();
	tot=1;
	for(re int i=1;i<=m;i++){
		int uu=read(),vv=read();LL ww=read_ll();
		kkk(uu,vv,ww),kkk(vv,uu,0LL);
	}
	dinic();
	printf("%lld",maxflow);
} 

end