首页
关于
笔记
文章
友链

Note -「Flows」

cirnovsky /

基本没有严谨证明。

∆ Part. 1 概念

Part. 1-1 流网络

流网络是一个有向图（不考虑反向边），我们把这个图记为 G=(V,E)G=(V,E)。

其中有两个特殊的点 s,ts,t，分别成为源点和汇点。

对于每一个 (u,v)∈E(u,v)\in E，我们给它两个属性，一个 c(u,v)c(u,v)，表示这条边的容量；一个 f(u,v)f(u,v)，表示这条边的流量。

每一条边都需要满足两个性质：

  • 容量限制，0≤f(u,v)≤c(u,v)0\le f(u,v)\le c(u,v)。
  • 流量守恒，∑(x,u)∈Ef(x,u)=∑u,y∈Ef(u,y)\sum_{(x,u)\in E}f(x,u)=\sum_{u,y\in E}f(u,y)，即流进来多少流出去多少。

（这里的定义是 yxc / 算导 的定义，和网络上大部分的资料不同）

我们称一个网络的可行流的流量为 (∑(s,x)∈Ef(s,x))−(∑(y,s)∈Ef(y,s))\left(\sum_{(s,x)\in E}f(s,x)\right)-\left(\sum_{(y,s)\in E}f(y,s)\right)，即流出源点的流量减去流入源点的流量。

一个可行流的方案我们记为 ff，其流量记为 ∣f∣|f|。

Part. 1-2 残量网络

残量网络即把原网络的反向边算进去，把反向边的边集记为 E′E'，把残量网络表示为 Gf=(V,E∪E′)G_{f}=(V,E\cup E')，把残量网络的一个可行流方案记为 f′f'，同理 ∣f′∣|f'|，cf(u,v)c_{f}(u,v)，f′(u,v)f'(u,v)。

这里定义 ff 之间的加法：

首先我们知道对于 GG 的每一个不同的 ff 而言，其 G′G' 是不同的。

我们定义 {c'(u,v)=\begin{cases}c(u,v)-f(u,v),(u,v)\in E \\ \displaystyle f(v,u),(u,v)\in E'\end{cases}。

那么 ff 之间的加法是这样定义的：f′(u,v)=f′(u,v)+f(u,v),f′(v,u)=f′(v,u)−f(u,v)f'(u,v)=f'(u,v)+f(u,v),f'(v,u)=f'(v,u)-f(u,v)。（定义不太清楚，自行意会吧）

然后可以证明 ∣f+f′∣=∣f∣+∣f′∣|f+f'|=|f|+|f'|，注意 ∣f′∣|f'| 可能为负。

Part. 1-3 增广路

增广路就是一条从 ss 到 tt 的简单路径，满足路上每条边的容量都 >0>0。

Part. 1-4 割

割是对 VV 进行的划分。

首先我们划分出两个集合 S,TS,T，需满足 s∈S,t∈Ts\in S,t\in T 且 S∪T=V,S∩T=∅S\cup T=V,S\cap T=\empty。

我们再定义割的容量：c(S,T)=∑u∈S∑v∈Tc(u,v)c(S,T)=\sum_{u\in S}\sum_{v\in T}c(u,v)（不考虑反向边）。

割的流量：f(S,T)=(∑u∈S∑v∈Tf(u,v))−(∑u∈S∑v∈Tf(v,u))f(S,T)=\left(\sum_{u\in S}\sum_{v\in T}f(u,v)\right)-\left(\sum_{u\in S}\sum_{v\in T}f(v,u)\right)。

这里流量和容量的定义不对称，不过 不 影 响。

可以证明对于任意可行流的任意割，有 f(S,T)≤c(S,T)f(S,T)\le c(S,T)，也有 ∣f∣=f(S,T)≤c(S,T)|f|=f(S,T)\le c(S,T)。

最小割指容量最小的割。

Part. 1-5 最大流最小割定理

  • 可行流 ff 为最大流
  • 对于可行流 ff，其 GfG_{f} 不存在增广路。
  • 存在割 [S,T][S,T]，∣f∣=c(S,T)|f|=c(S,T)。

以上三条可以互相推出。

最大流等于最小割。

∆ Part. 2 算法

Part. 1-1 Edmond-Karp

不会

Part. 1-2 Dinic

先讲讲暴力 FF。

算了懒得讲了自己看洛谷题解的暴力代码吧。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10010, E = 200010;

int n, m, s, t;
LL first[N];
LL to[E], nxt[E], val[E]/*残余容量*/;
int cnt = 1;
//cnt初值1，第一条边的标号为2（二进制10），第二条是3（二进制11） 
//有啥好处呢？
//我们加入一条边时，紧接着加入它的反向边（初始容量0） 
//这两条边的标号就是二进制最后一位不相同，一个0、一个1
//所以要召唤 p 这条边的反向边，只需用 p ^ 1
//如果cnt初值为0，就做不到。当然初值-1也可以，略需改动

//关于图中真正的反向边，可能引起顾虑，应该让它们标号相邻？ 
//其实不用。该找到的增广路都会找到的 

bool vis[N];//限制增广路不要重复走点，否则很容易爆栈 
//兜一大圈走到汇点，还不如直接走到汇点

void addE(int u, int v, LL w) {
	++cnt;
	to[cnt] = v;
	val[cnt] = w;
	nxt[cnt] = first[u];
	first[u] = cnt;
}
LL dfs(int u, LL flow) {
	//注意，在走到汇点之前，无法得知这次的流量到底有多少 
	if (u == t)
		return flow;//走到汇点才return一个实实在在的流量 
	
	vis[u] = true;
	for (int p = first[u]; p; p = nxt[p]) {
		int v = to[p];
		if (val[p] == 0 or vis[v])//无残量，走了也没用 
			continue;
		int res = 0;
		if ((res = dfs(v, min(flow, val[p]))) > 0) {
			//↑顺着流过去，要受一路上最小容量的限制
			val[p] -= res;//此边残余容量减小
			val[p ^ 1] += res;//以后可以顺着反向边收回这些容量，前提是对方有人了 
			return res;
		}
	}
	return 0;//我与终点根本不连通（依照残量网络），上一个点不要信任我
}
int main() {
	scanf("%d %d %d %d", &n, &m, &s, &t);
	for (int i = 1; i <= m; ++i) {
		int u, v; LL w;
		scanf("%d %d %lld", &u, &v, &w);
		addE(u, v, w);
		addE(v, u, 0);//和正向边标号相邻
		//反向边开始容量为0，表示不允许平白无故走反向边
		//只有正向边流量过来以后，才提供返还流量的机会
	}
	LL res = 0, tot = 0;
	while (memset(vis, 0, sizeof(vis)) and (res = dfs(s, 1e18/*水库无限*/)) > 0)
		tot += res;//进行若干回合的增广

	printf("%lld\n", tot);
	return 0;
}

接下来讲讲如何 Dinic。

其实我不理解 Dinic 比暴力优在哪里

/* okay | there's been */

#include <cstdio>

namespace mySpace {
typedef long long LL;

const int MAXN = 200 + 5, MAXM = 5000 + 5;

int rint () {
	int x = 0, f = 1; char c = getchar ();
	for ( ; c < '0' || c > '9'; c = getchar () )	f = c == '-' ? -1 : f;
	for ( ; c >= '0' && c <= '9'; c = getchar () )	x = ( x << 3 ) + ( x << 1 ) + ( c & 15 );
	return x * f;
}

template<typename _T> _T MIN ( const _T x, const _T y ) { return x < y ? x : y; }

struct GraphSet {
	int to, nx;
	LL wt;
	GraphSet () : to ( 0 ), nx ( 0 ), wt ( 0 ) {}
	GraphSet ( const int a, const int b, const LL c ) : to ( a ), nx ( b ), wt ( c ) {}
} as[MAXM * 2];

int n, m, s, t, bgn[MAXN], cnt = 1, lav[MAXN], ali[MAXN];

void makeEdge ( const int u, const int v, const LL w ) { as[++ cnt] = GraphSet ( v, bgn[u], w ), bgn[u] = cnt; }

bool bfs () {
	for ( int i = 1; i <= n; ++ i )	lav[i] = 0;
	int nowl = 1, nowr = 1;
	ali[1] = s, lav[s] = 1;
	for ( ; nowl <= nowr; ) {
		int u = ali[nowl ++];
		for ( int i = bgn[u]; i; i = as[i].nx ) {
			int v = as[i].to; LL w = as[i].wt;
			if ( ! w || lav[v] )	continue;
			lav[v] = lav[u] + 1, ali[++ nowr] = v;
		}
	}
	return lav[t];
}

LL dfs ( const int u, LL in ) {
	if ( u == t )	return in;
	LL out = 0;
	for ( int i = bgn[u]; i; i = as[i].nx ) {
		if ( ! in )	break;
		int v = as[i].to; LL w = as[i].wt;
		if ( ! w || lav[v] != lav[u] + 1 )	continue;
		LL ret = dfs ( v, MIN ( in, w ) );
		as[i].wt -= ret, as[i ^ 1].wt += ret;
		in -= ret, out += ret;
	}
	if ( ! out )	lav[u] = 0;
	return out;
}

LL calcMXflow () {
	LL res = 0;
	for ( ; bfs (); res += dfs ( s, 1e18 ) ) ;
	return res;
}

void main () {
	n = rint (), m = rint (), s = rint (), t = rint ();
	for ( int i = 1; i <= m; ++ i ) {
		int u = rint (), v = rint (); LL w = rint ();
		makeEdge ( u, v, w ), makeEdge ( v, u, 0 );
	}
	printf ( "%lld\n", calcMXflow () );
}
}

int main () {
	mySpace :: main ();
	return 0;
}

∆ Part. 3 无源汇上下界可行流

Part. 3-1 概念

就是每条边的容量从变成了 [cl(u,v),cr(u,v)][cl(u,v),cr(u,v)]。

Part. 3-2 xxxx

可以想见通过把容量转化为 [0,cr(u,v)−cl(uv)][0,cr(u,v)-cl(uv)]，但这样容量不一定能守恒。

记每个点的入流量为 inuin_{u}，出流为 outuout_{u}。

  • inu≥outuin_{u}\ge out_{u}

从 SS 向 uu 连一条容量 inu−outuin_{u}-out_{u} 的边。

  • inu<outuin_{u}<out_{u}

从 uu 向 TT 连一条容量 outu−inuout_{u}-in_{u} 的边。

∆ Part. 4 有源汇上下界最大流

Part. 4-1 概念

有规定的源点汇点了。

Part. 4-2 xxxx

图都是从 这里 偷的。这个博客几百年没过图了

20190824120232582.png

有源汇后，ss 和 tt 不满足流量守恒了，于是从 ss 到 tt 连一条容量 [0,∞][0,\infty] 的边即可。

20190824120304124.png

然后就可以把 ss 和 tt 当成普通点处理，重现建立超源超汇，用无源汇上下界可行流的方法跑一遍，看是不是一个可行流，如果是就从 ss 到 tt 跑一遍最大流。

∆ Part. 5 有源汇上下界最小流

Part. 5-1 概念

你猜。

Part. 5-2 xxxx

首先加上 (t,s)(t,s) 的边跑最大流。

设 dd 是加上的边的流量，删掉加上的边。

答案是 d−maxflow(t,s)d-\text{maxflow}(t,s)。

从 这里 copy 的。

∆ Part. 6 多源汇最大流

Part. 6-1 概念

你猜。

Part. 6-2 xxxx

没啥区别，建超源超汇即可。