最大流

最大流问题

有向图 G 中，有两个特殊的点，源点和汇点，每条边有指定的容量，求S到T的最大流。

就像从源点放水，水量无穷大，汇点的水量是多少？

定义

c为容量，f为流量

流量守恒

\(f(x,y)\leq c(x,y)\)

容量性质

\(\sum f(u,x) = \sum f(x,u)\)

斜对称性

\(f(x,y) = -f(y,x)\)

容量网络，流量网络

残留网络=容量网络-流量网络，连两条边

增广路：残留网络上从源点到汇点的简单路径

反向弧：给算法“返悔的机会”

增广路定理：当前流为最大流的充要条件是无增广路

Ford-Fulkerson 方法

Edmonds-Karp 算法

残留流量为正，BFS

\(O(VE^2)\)

Dinic 算法

分层网络，用DFS一次求解多个增广路

BFS分层，DFS多路增广，当前弧优化：一个点被dfs两次，而接上去的前几个点无法增广，所以记录当前弧

正常时 \(O(V^2E)\)

二分图时 \(O(\sqrt{V}E)\)

实现

斜对称修改

u->v的边要记录v->u的边的下标。

链式前向星只需要把下标换成从2开始，异或1 tot=1

int dinic(){
	int res=0;
	while(dinic_bfs())res+=dinic_dfs(S,INF);
	return res;
}

bool dinic_bfs(){
	for(int i=1;i<=T;++i)h[i]=oh[i],level[i]=0;
	queue<int> q;
	q.push(S);
	level[S] = 1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=h[x];i;i=e[i].ne){
			int y=e[i].to;
			if(!level[y]&&e[i].c>e[i].f){
				level[y] = level[x]+1;
				q.push(y);
			}
		} 
	}
	return level[T]!=0;
}

int dinic_dfs(int x,int cp){
	if(x==T)return cp;
	int tmp=cp;
	for(int &i=h[x];i;i=e[i].ne){//邻接表
		int y=e[i].to;
		if(level[y]==level[x]+1&&e[i].c>e[i].f){
			int t=dinic_dfs(y,min(tmp,e[i].c-e[i].f));//记住流量要实时减少tmp而非cp
			e[i].f += t;e[i^1].f -= t;
			tmp -= t;
			if(tmp==0)break;//当前弧更换要注意可能是tmp不够了而不是无法增广，所以不能放在for的条件判断上
		}
	}
	return cp-tmp;
}

实际应用（建模）

常用构图方式

S->T流对应原题中的方案

拆点

餐厅一题：拆点

状态表示优化

猪圈问题：一轮建m+1个点，顾客和m个猪圈，跑最大流

优化：一个好几轮没打开的猪圈，出边入边相同，可以合并

多个人使用同一个猪圈，则在他们顾客之间连无穷大的边，省去猪圈的点，和很多很多边，然后从顾客连出去边，符合题意中“特定数量”

行列建点

打扫卫生：行列建点

转化为二分图最小顶点覆盖

马：坏的格子不用连，二分图最大独立集

割

流网络 割 \((S,T)\) 分成 \(S\) 和 \(T=V-S\) 两个部分

割的容量不算反方向，净流量算反方向

最大流等于最小割定理

二分图性质

二分图匹配，选边，两两间没有公共点（匹配）

二分图最小顶点覆盖，选点，每条边至少有一个端点被选出（覆盖集）

二分图最大独立集，选点，点两两间没有边相连（独立集）

1. 因为网络流的模型相同，根据最大流最小割定理，二分图最小点覆盖等于最大匹配。

2. 二分图最大独立集等于总点数减去最小覆盖集。

通过反证，先证充分性，去掉独立集如果不是覆盖集，那么独立集间有边相连，矛盾。再证必要性，覆盖集一定占据了任意一条边的一个端点，那么独立集一定没有相连的边。（充分必要逻辑有问题）

最大权闭合子图问题

一些项目做了会赚钱，一些员工雇佣要花钱。一个项目需要指定的员工，一个员工雇佣后可以参加任意多项目，问经过项目取舍，最多可以挣多少钱？

可以建模成图，一个点选了，则出边都要选。建立网络流模型，原点向项目连边，员工向汇点连边，中间边权无穷大。应当在图上求最小割。

如果 \(S->P\) 没有被割且 \(P->Q->T\) 没有被割，则选了项目没有选人，不合法，而建模与题意吻合，跑最小割。

建模总结

数学研究性质，信息解决问题。

数学善于建立定理，概念。理念和建模是两码事，要符合实际问题。