网络流总结

发布时间:2024年01月02日

基础知识

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

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

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

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

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

\qquad 流网络中的指的是将图中的所有点分为 S , T S,T S,T 两个点集,记作 C ( S , T ) C(S,T) C(S,T)。这两个点集要满足:1、 s ∈ S , t ∈ T s\in S,t\in T sS,tT;2、 S ∩ T = ? S\cap T=\emptyset ST=?;3、 S ∪ T = V S\cup T=V ST=V。割的容量定义为: ∑ u ∈ S , v ∈ T c ( u , v ) \sum_{u\in S,v\in T}c(u,v) uS,vT?c(u,v),割的流量定义为: ∑ u ∈ S , v ∈ T f ( u , v ) ? ∑ u ∈ T , v ∈ S f ( u , v ) \sum_{u\in S,v\in T}f(u,v)-\sum_{u\in T,v\in S}f(u,v) uS,vT?f(u,v)?uT,vS?f(u,v)。流网络中的最小割指的是容量最小

最大流最小割定理

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

最大流

\qquad 求最大流有两种算法: E K EK EK d i n i c dinic dinic

EK

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

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

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 E K EK EK 的基础之上,我们考虑优化。

\qquad E K EK EK 每次 b f s bfs bfs 只找出来了一条增广路进行增广,效率较低。 d i n i c dinic dinic 算法依据分层思想,每次找出多条增广路同时进行增广,而且还有三处小优化,总体时间复杂度 O ( n 2 m ) O(n^2m) O(n2m)不过法律规定网络流不许卡 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 n n 个点 m m m 条边的有向图,每条边都有一个流量下界和流量上界。求一种可行方案使得在所有点满足流量平衡条件的前提下,所有边满足流量限制。

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

\qquad 核心 C o d e Code 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 面对上下界,我们可以考虑建一条从汇点指向源点,容量为 I N F INF INF 的边,这样就转化为了无源汇上下界问题。我们可以先沿用无源汇上下界可行流的算法跑出一个可行流,然后将新添的边删去,再从源点向汇点跑出一个最大流,将这两个流相加便是答案。证明我也不太会……

\qquad 核心 C o d e Code 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 对于最小流,我们让上述代码输出 r e s ? d i n i c ( ) res-dinic() res?dinic() 即可。证明我还是不会……

多源汇最大流

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

最大流之关键边

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

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

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

最大流之拆点

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

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

最大流建图实战

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

最小割

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

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

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

模型

最大权闭合子图

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

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

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

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

最大密度子图

\qquad 我们定义一个图 G = ( V , E ) G=(V,E) G=(V,E) 的密度为 ∣ E ∣ ∣ V ∣ \frac{|E|}{|V|} VE?,最大密度子图指的便是图 G G G 中使得 ∣ E ′ ∣ ∣ V ′ ∣ \frac{|E'|}{|V'|} VE? 最大的子图 G ′ = ( V ′ , E ′ ) G'=(V',E') G=(V,E)

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

\qquad 核心 C o d e Code 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;
}
文章来源:https://blog.csdn.net/x052xiao/article/details/135298519
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。