网络流总结

基础知识

\qquad 流网络是一个有源点 $s$ 和汇点 $t$ 的有向图（不考虑反向边），记为 $G=(V,E)$。其中每一条边都有一个容量 $c(u,v)$ 和一个流量 $f(u,v)$。对于该网络中的一个流 $f$，如果其满足两个条件：1、容量限制，即每条边都满足 $0\le f(u,v)\le c(u,v)$；2、流量守恒，即除去源点汇点以外，每个点 $x$ 都满足 ${\sum }_{u\in V}f(u,x)={\sum }_{v\in V}f(x,v)$，那么我们称流 $f$ 是流网络 $G$ 的一个可行流。可行流的流量 $|f|={\sum }_{u\in V}f(s,u)?{\sum }_{v\in V}f(v,s)$，即从源点流出的流量减去流入源点的流量。

\qquad 残留网络是针对于原图中的一个流来说的。即，我们只能说“流 $f$ 的残留网络 $G_f$”。残留网络对于原图中的每一条边都增加一条反向边，这条反向边的流量与原图中边的流量相等。可以将残留网络中的边理解为“退流”。

\qquad 两个可行流是可以相加减的，叠加的方式就是每条边上的流量对应相加减，而且得到的结果也一定是原图的一个可行流。

\qquad 如果一个流网络中存在一条路径，这条路径中的任意一条边都没有达到满流（即 $f(u,v)<c(u,v)$），那么我们称这条路径为一条增广路径。

\qquad 流网络中的最大流指的是最大可行流，即第一要满足此流是一条可行流，其次要满足它的流量是本图所有可行流中最大的一个。

\qquad 流网络中的割指的是将图中的所有点分为 $S,T$ 两个点集，记作 $C(S,T)$。这两个点集要满足：1、$s\in S,t\in T$；2、$S\cap T=?$；3、$S\cup T=V$。割的容量定义为：${\sum }_{u\in S,v\in T}c(u,v)$，割的流量定义为：${\sum }_{u\in S,v\in T}f(u,v)?{\sum }_{u\in T,v\in S}f(u,v)$。流网络中的最小割指的是容量最小。

最大流最小割定理

\qquad 最大流最小割定理包含三条内容，这三条内容知一推二，分别是：1、可行流 $f$ 是最大流；2、可行流 $f$ 的残留网络中不存在增广路；3、存在某个割 $C(S,T)$，满足 $|f|=C(S,T)$。

最大流

\qquad 求最大流有两种算法：$EK$ 和 $dinic$。

EK

\qquad 根据最大流最小割定理，我们可以得知，当残留网络中不存在增广路时，该残留网络对应的流 $f$ 一定是最大流。$EK$ 算法便是基于这个原理，每次 $bfs$ 找残留网络中的增广路并将其增广，直到网络中不存在增广路为止。

\qquad $EK$ 算法时间复杂度为 $O(n{m}^2)$，不过网络流算法记时间复杂度用处不大。思路很简单，实现也很容易。

const int maxn = 110;
const int maxm = 5010;
typedef long long LL;
int n, m, S, T;
struct pic {
	int to, lst;
	LL cap;
}edge[maxm << 1];
int head[maxn], tot = -1/*边从0开始编号，目的是方便成对变换*/, pre[maxn]/*记录每个点第一次被搜到的前驱边是哪一条*/;
queue < int > q;
LL d[maxn];//记录到达当前点时当前增广路径的最大流量

inline void add(int x, int y, int z) {
	edge[++ tot] = {y, head[x], 1LL * z};
	head[x] = tot;
}

bool bfs() {//寻找增广路
	memset(vis, 0, sizeof vis);
	while(!q.empty()) q.pop();
	q.push(S), vis[S] = 1, d[S] = 1e9 + 7;
	while(!q.empty()) {
		int x = q.front(); q.pop();
		for(int i = head[x]; ~i; i = edge[i].lst) {
			int y = edge[i].to;
			if(!vis[y] && edge[i].cap/*有流量时才有意义去搜*/) {
				d[y] = min(d[x], edge[i].cap);//更新最大流量
				vis[y] = 1, pre[y] = i;
				if(y == T) return 1;//找到了一条增广路
				q.push(y);
			}
		}
	}
	return 0;
}

LL EK() {
	LL ans = 0;
	while(bfs()) {
		ans += d[T];
		for(int x = T; x != S; x = edge[pre[x] ^ 1/*成对变换*/].to) edge[pre[x]].cap -= d[T], edge[pre[x] ^ 1].cap += d[T];//对增广路进行增广操作
	}
	return ans;
}
//main中
memset(head, -1, sizeof head);
scanf("%d%d%d%d", &n, &m, &S, &T);
for(int i = 1, x, y, z; i <= m; i ++) {
	scanf("%d%d%d", &x, &y, &z);
	add(x, y, z), add(y, x, 0)/*建残留网络，一开始流量都是0*/;
}
printf("%lld\n", EK());
}

dinic

\qquad 在 $EK$ 的基础之上，我们考虑优化。

\qquad $EK$ 每次 $bfs$ 只找出来了一条增广路进行增广，效率较低。$dinic$ 算法依据分层思想，每次找出多条增广路同时进行增广，而且还有三处小优化，总体时间复杂度 $O(n^{2}m)$，不过法律规定网络流不许卡 dinic。

bool bfs() {//找增广路
	memset(d, -1, sizeof d);//分层
	while(!q.empty()) q.pop();
	d[1] = 0/*源点层数为0*/, q.push(1), cur[1] = head[1];//当前弧优化
	while(!q.empty()) {
		int x = q.front(); q.pop();
		for(int i = head[x]; ~i; i = edge[i].lst) {
			int v = edge[i].to; LL w = edge[i].cap;
			if(d[v] == -1 && w) {
				d[v] = d[x] + 1/*记录点v在点x下一层*/, cur[v] = head[v];//记录从哪一条边开始跑
				if(v == n) return 1;
				q.push(v);
			}
		}
	}
	return 0;
}

LL Find(int x, LL limit) {//limit:当前增广路径的最大流量
	if(x == n) return limit;//到了汇点
	LL flow = 0;//增广了多少流量
	for(int i = cur[x]; ~i && flow < limit/*优化1（最重要）：当flow>limit，再搜下去就无意义了，因为无法继续增广了*/; i = edge[i].lst) {
		cur[x] = i;//优化2：当前弧优化
		int v = edge[i].to; LL w = edge[i].cap;
		if(d[v] == d[x] + 1/*判断点v是否是点x的下一层*/ && w) {
			LL t = Find(v, min(w, limit - flow));
			if(!t) d[v] = -1;//优化3：如果这个点往后的流量是0，说明通过此点无法进行增广，直接删除即可
			edge[i].cap -= t, edge[i ^ 1].cap += t, flow += t;
		}
	}
	return flow;
}

LL dinic() {
	LL flow = 0, ans = 0;
	while(bfs()) while(flow = Find(1, INF)) ans += flow;
	return ans;
}

模型

二分图匹配

\qquad 例题：飞行员配对方案问题，圆桌问题。

\qquad 套路：用最大流中边的容量来对边进行限制。

无源汇上下界可行流

\qquad 问题：给定一个包含 $n$ 个点 $m$ 条边的有向图，每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。

\qquad 对于上下界的限制，形式化写出来是：$c_{low}(u,v)\le f(u,v)\le c_{up}(u,v)$，我们可以选择让不等式同时减去 $c_{low}(u,v)$ 从而变成只有上界的问题。但是减完之后可能会有点不满足流量守恒，此时我们需要建立超级源点、超级汇点，根据每个点是少流还是多流来对它们进行补偿或减少（即与源点连还是与汇点连）。而且为了保证这些点一定流量守恒，与源点、汇点相连的边必须要是满流的。所以我们连好与超级源点、汇点的边后，直接在新网络上跑最大流，如果跑出来的不是满流，那么原问题一定无解；否则，让新网络中每条边的流量加上原来的下界，就是原问题的一个可行流。

\qquad 核心 $Code$：

for(int i = 1, a, b, c, d; i <= m; i ++) {
	scanf("%d%d%d%d", &a, &b, &c, &d);
	add(a, b, d - c/*减去下节*/, c/*同时储存下界*/), add(b, a, 0, 0);
	A[a] -= c, A[b] += c;//记录每条边减去下界后，每个点流量的变化
}
int all = 0;
for(int i = 1; i <= n; i ++) {
	if(A[i] > 0) add(S, i, A[i], 0), add(i, S, 0, 0), all += A[i];//少流了，需要补
	else if(A[i] < 0) add(i, T, -A[i], 0), add(T, i, 0, 0);//多留了，需要放
}
if(dinic() < all) puts("NO");//不满流，无解
else {
	puts("YES");
	for(int i = 1; i <= (m << 1); i += 2) printf("%d\n", edge[i].cap + edge[i ^ 1].lower);//加上下界
}

有源汇上下界最大、最小流

\qquad 面对上下界，我们可以考虑建一条从汇点指向源点，容量为 $INF$ 的边，这样就转化为了无源汇上下界问题。我们可以先沿用无源汇上下界可行流的算法跑出一个可行流，然后将新添的边删去，再从源点向汇点跑出一个最大流，将这两个流相加便是答案。证明我也不太会……

\qquad 核心 $Code$：

for(int i = 1, a, b, c, d; i <= m; i ++) {
	scanf("%d%d%d%d", &a, &b, &c, &d);
	add(a, b, d - c), add(b, a, 0);
	A[a] -= c, A[b] += c;
}
int all = 0;
for(int i = 1; i <= n; i ++) {
	if(A[i] > 0) add(S, i, A[i]), add(i, S, 0), all += A[i];
	else if(A[i] < 0) add(i, T, -A[i]), add(T, i, 0);
}
add(t, s, INF), add(s, t, 0);//添加一条t->s，INF的边
if(dinic() < all) puts("No Solution");
else {
	int res = edge[tot].cap;//跑出来的可行流，注意不是dinic返回的流，因为dinic返回的是S到T的，我们需要的是s到t的
	edge[tot].cap = edge[tot ^ 1].cap = 0, S = s, T = t;
	printf("%d\n", res + dinic());
}

\qquad 对于最小流，我们让上述代码输出 $res?dinic()$ 即可。证明我还是不会……

多源汇最大流

\qquad 超级源点指向各个源点，各个汇点指向超级汇点，然后跑最大流即可。

最大流之关键边

\qquad 问题：如果升高一条边的容量可以使得最大流变大，那么我们称这条边为“关键边”。现在求网络中有几条“关键边”。

\qquad 我们思考，什么样的边可以成为关键边？

\qquad 在跑完最大流后，如果存在一条路径，这条路径中只有一条边是满流的，那么这条边一定是关键边。证明也很显然。那么，我们只需跑完最大流后，分别从源点和汇点开始 $dfs$，每次只走没满流的边。搜完之后，如果一条边的两端点分别被源点和汇点搜到，那么它一定是关键边。

最大流之拆点

\qquad 当我们有时要对点进行限制时，我们可以考虑拆点，在拆出的点之间加边来满足对点的限制。

\qquad 例题：[USACO07OPEN] Dining G，最长不下降子序列问题。

最大流建图实战

\qquad 例题：MPIGS - Sell Pigs，[SCOI2007] 蜥蜴，清理雪道。

最小割

\qquad 根据“最大流最小割定理”，我们可以得知，网络中最小割的容量就是最大流的流量，所以我们完全可以用求最大流的方法求最小割。

\qquad 但是，如果让求最小割的方案，怎么办呢？

\qquad 参考最大流求关键边的做法，我们可以从源点开始 $dfs$，每次只走没满流的边。最后如果有一条边的两个端点有一个被搜到了，另一个没有，那么这条边就要被割开。这也就意味着，整个图可以被分为“被搜到的点”和“没被搜到的点”两个点集。这样，其中一个合法方案就求出来了。

模型

最大权闭合子图

\qquad 对于图 $G=(V,E)$，如果它的一个子图 $G^{\prime }=(V^{\prime },E^{\prime })$ 满足 $V^{\prime }$ 中的任意一个点的任意一条出边都在 $E^{\prime }$ 内，那么就称 $G^{\prime }$ 是 $G$ 的一个闭合子图。如果给每个点附上点权（可为负），那么点权最大的一个闭合子图称为最大权闭合子图。

\qquad 如果给出一个带点权的图，我们怎么求解它的最大权闭合子图呢？

\qquad 首先，我们分别建立超级源点、超级汇点，超级源点指向所有正点权的点，边权为这个点的点权；所有负点权的点指向超级汇点，边权为这个点点权的绝对值；对于原图中的边，正常建在网络上，边权为 $INF$。此时，我们设所有正点权的点的点权和为 $r$。建好图之后，在图上跑一个最小割，设这个最小割的权值是 $s$，那么原图的最大权闭合子图的权值便是 $r?s$。

\qquad 例题：[NOI2006] 最大获利，太空飞行计划问题。

最大密度子图

\qquad 我们定义一个图 $G=(V,E)$ 的密度为 $\frac{|E|}{|V|}$，最大密度子图指的便是图 $G$ 中使得 $\frac{|E^{\prime }|}{|V^{\prime }|}$ 最大的子图 $G^{\prime }=(V^{\prime },E^{\prime })$。

\qquad 既然是要让一个分式最大，那么就一定要用到 $0/1$ 分数规划。设当前二分的值为 $g$，那么我们就要尽可能找到 $|E^{\prime }|?g|V^{\prime }|$ 的最大值。在求最大值的过程中，我们可以借助最小割来推导式子并求解。

\qquad 核心 $Code$：

bool check(db x) {
	memset(head, -1, sizeof head), tot = -1;
	for(int i = 1; i <= m; i ++) add(E[i].first, E[i].second, 1), add(E[i].second, E[i].first, 1);
	for(int i = 1; i <= n; i ++) add(S, i, m), add(i, S, m), add(i, T, 1.0 * m + 2 * x - du[i]), add(T, i, 1.0 * m + 2 * x - du[i]);
	return 1.0 * m * n - dinic() > 0.0;
}