网络流 复习笔记

网络流是图论中的经典问题，应用非常广泛，思想并不难理解，但实现部分大部分文章都不够详细，导致蒟蒻君学的时候就看了很长时间，这篇文章会较为详细的阐述细节部分。

最大流

问题

有向带权图中，每一条弧（注意这里不能叫边…）$<u,v>$权值为$w$，含义为$u$到$v$的容量，即最大能流过去的量，为$w$。有源点$S$和汇点$T$，表示要从$S$流到$T$，问最多能流多少。

$\to$

如图，左为容量，右为流量。

这里先给出一些定义。

• 容量：一条弧上的最大流量，记为$c(u,v)$；
• 流量：实际流的量，记为$f(u,v)$；
• 饱和弧：流满，即$f(u,v)=c(u,v)$；
• 零流弧：没流，即$f(u,v)=0$；
• 容量网络：对于有向带权图$G(V,E)$，有指定$S,T\in V$，表示源点和汇点；对于$\forall <u,v>\in E$，有$c(u,v)>0$；
• 网络流：所有$f(u,v)$的集合；
• 可行流：可行的网络流；
• 最大流：总流量最大的可行流。

那可行流具体要满足什么条件呢？

1. 对于$\forall <u,v>\in E$，有$0\le f(u,v)\le c(u,v)$；
2. 对于$u\in V$，有 从 u 流出的量 − 流入 u 的量 = { u = V s → ∣ f ∣ u ≠ V s , u ≠ V t → 0 u = V t → − ∣ f ∣ 从u流出的量-流入u的量=\left\{
   u=Vs→|f|u≠Vs,u≠Vt→0u=Vt→−|f|" role="presentation" style="position: relative;">u=Vsu≠Vs,u≠Vtu=Vt→|f|→0→−|f|$$\begin{array}{ll}u=V_s& \to |f|\\ u\ne V_s,u\ne V_t& \to 0\\ u=V_t& \to -|f|\end{array}$$
   \right. 从u流出的量−流入u的量=⎩ ⎨ ⎧​u=Vs​u=Vs​,u=Vt​u=Vt​​→∣f∣→0→−∣f∣​

对于任何容量网络，总是存在可行流，如全为零流。

EK

这里还会有些定义。

• 链：顶点序列中相邻两点均要有弧连接（这里不限制方向），其方向为$S$到$T$。

• 前向弧：与链方向相同的弧，即沿着链，经过这条弧时按其方向走，能从$S$走到$T$。注意这里弧的方向是对于指定链的，令链为$P$，则前向弧记为$P^{+}$；

• 后向弧：与链方向相反的弧，记为$P^{-}$。

  这里举个例子。

  

  如图，此时链为 P = { S , 1 , 2 , 3 , T } P=\{S,1,2,3,T\} P={S,1,2,3,T}，则 P + = { < S , 1 > , < 2 , 4 > , < 4 , T > } P^+=\{,<2,4>,<4,T>\} P+={<S,1>,<2,4>,<4,T>}， P − = { < 2 , 1 > } P^-=\{<2,1>\} P−={<2,1>}，当然，一条弧的方向对于不同的链可能是不同的，如对于链 P ′ = { S , 2 , 4 , T } P'=\{S,2,4,T\} P′={S,2,4,T}，弧$<2,1>$为正向弧。

• 增广路

  若有链$P$，从$S$到$T$，任意一条弧都有剩余容量，即对于所有$<u,v>$，有$f(u,v)<c(u,v)$，这样的$P$显然可以通过让所有弧的流量都加上最小的$c(u,v)-f(u,v)$使最大流更大。

• 残量

  表示只考虑当前弧合法的情况下还可以增加的流量，即$c^{\prime }(u,v)=c(u,v)-f(u,v)$。

• 残量网络

  对于容量网络$G(V,E)$，令其残量网络为$G^{\prime }(V^{\prime },E^{\prime })$，

  其中$V^{\prime }=V$；

  对于弧$<u,v>\in E$：

  • 若有$f(u,v)<c(u,v)$，则有$<u,v>\in E^{\prime }$，$c^{\prime }(u,v)=c(u,v)-f(u,v)$；
  • 若有$f(u,v)>0$，则有$<v,u>\in E^{\prime }$，$c^{\prime }(v,u)=f(u,v)$。

想必大家已经知道EK算法的核心思想了：构建残量网络，不断bfs寻找增广路，只要存在，流量就可以增大；否则，当前流就是最大流，复杂度为$O(V{E}^2)$。

#include 
using namespace std;
const int N = 205, M = 405;
struct edge {
	int u, v, c, nxt;	// c: c'，即剩余可用流量
} e[M];
int head[N], cnt, S, T;
inline void add(int u, int v, int c) {
	e[++cnt] = {u, v, c, head[u]}, head[u] = cnt;
}
inline void adde(int u, int v, int c) {
	add(u, v, c), add(v, u, 0);
}
int E[N]; // E[u]: 到达u以到达T的边的编号
bool bfs() {	// 返回值：是否找到增广路
	queue<int> q;
	q.push(S);
	memset(E, -1, sizeof E);
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (E[v] == -1 && e[i].c) {   // 若v未访问且目前弧非零流
				E[v] = i;
				if (v == T) {
					break;
				}
				q.push(v);
			}
		}
		if (E[T] != -1) {	// 成功到达T，即找到增广路
			return 1;
		}
	}
	return 0;
}
int EK() {
	int res = 0;
	while (bfs()) {
		int del = 1e9;	// del: 增广路中最小c'，即最大流增加的量
		for (int i = T; i != S; i = e[E[i]].u) {
			del = min(del, e[E[i]].c);
		}
		for (int i = T; i != S; i = e[E[i]].u) {	// 因为是剩余所以正减反加
			e[E[i]].c += del;
			e[E[i] ^ 1].c -= del;
		}
		res += del;
	}
	return res;
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, c;
		cin >> u >> v >> c;
		adde(u, v, c);
	}
	cin >> S >> T;
	cout << EK() << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

Dinic

相当于EK的优化，不同之处有以下两点：

• bfs分层，寻找增广路时只会从深度为$d$的结点走到深度为$d+1$的，这样做避免了$G$中一条弧在$G^{\prime }$中变为两条时的影响；
• dfs多路增广，从每次只能找一条增广路变成多条。

复杂度为$O(V^{2}E)$。

#include 
using namespace std;
const int N = 105, M = 10005;
struct edge {
	int v, c, nxt;	// 这里c同样表示c'，即剩余可用流量
} e[M];
int head[N], cnt;
inline void add(int u, int v, int c) {
	e[++cnt] = {v, c, head[u]}, head[u] = cnt;
}
inline void adde(int u, int v, int c) {
	add(u, v, c), add(v, u, 0);
}
int S, T, d[N];	// d: 层数
bool bfs() {	// 返回值：是否还会有有增广路，即G'中存在一条S到T且流量非0的链P
	memset(d, -1, sizeof d);
	queue<int> q;
	q.push(S);
	d[S] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (d[v] == -1 && e[i].c) {	// 未访问过且顺序正确
				q.push(v);
				d[v] = d[u] + 1;
			}
		}
	}
	return d[T] != -1;
}
// 返回值：增量
int dfs(int u, int f) {	// f: 剩余可用流量，这里“可用”指还能增大，即最小的c'
	if (u == T) {
		return f;
	}
	int res = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].c) {
			int t = dfs(v, min(f, e[i].c));	// 增大的量
			e[i].c -= t;
			e[i ^ 1].c += t;
			res += t;
			f -= t;
			if (!f) {	// 不能增大就结束
				break;
			}
		}
	}
	if (res == 0) {	// 在非零流情况下不能到达点u，说明u已经无效，这样在判断顺序的时候会有效
		d[u] = -1;
	}
	return res;
}
int Dinic() {
	int res = 0;
	while (bfs()) {
		res += dfs(S, 1e9);
	}
	return res;
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, f;
		cin >> u >> v >> f;
		adde(u, v, f);
	}
	cin >> S >> T;
	cout << Dinic() << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

最小割

##问题

​ 额定义还是有点的。

• 割

  对于容量网络$G(V,E)$，删去一些边，使得$G$被划分为$S1$和$S2=V-S1$两部分，我们用$(S1,S2)$来表示一个割。

• $s-t$割

  对于一个割$(S1,S2)$，若源点$S\in S1$，汇点$T\in S2$，则称$(S1,S2)$为s-t割，称$<u,v>(u\in S1,v\in S2)$为前向弧，$<u,v>(u\in S2,v\in S1)$为后向弧。

• 割的容量

  对于容量网络$G(V,E)$和其s-t割$(S1,S2)$，令其容量为所有前向弧容量总和，记为$c(S1,S2)$。

• 最小割

  容量最小的s-t割。

给定容量网络，求其最小割的容量。

定理

结论

最小割的容量和最大流的流量相等。

证明

有引理：对于每个割，通过其中所有弧的流量之和是恒定的。

证明：显然，割中弧要阻拦住所有流量，所以对于所有割，通过其中所有弧的流量之和就是$S$的净流出量。

又有流量小于等于容量，所以任意流流量都会小于等于任意割的容量，对于最小割和最大流，就是等于。

实现

我们尝试求出$S1$，过程分为两步：

• 求出最大流；
• 在此时残量网络中搜索，能在流量非零条件下访问到的即为$S1$中的点。

这里注意一个地方，最小割中的弧一定满流，但满流弧不一定属于最小割。

#include 
using namespace std;
const int N = 105, M = 10005;
struct edge {
	int v, c, nxt;
} e[M];
int head[N], cnt;
inline void add(int u, int v, int c) {
	e[++cnt] = {v, c, head[u]}, head[u] = cnt;
}
inline void adde(int u, int v, int c) {
	add(u, v, c), add(v, u, 0);
}
int S, T, d[N];
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.push(S);
	d[S] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (d[v] == -1 && e[i].c) {
				q.push(v);
				d[v] = d[u] + 1;
			}
		}
	}
	return d[T] != -1;
}
int dfs(int u, int f) {
	if (u == T) {
		return f;
	}
	int res = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].c) {
			int t = dfs(v, min(f, e[i].c));
			e[i].c -= t;
			e[i ^ 1].c += t;
			res += t;
			f -= t;
			if (!f) {
				break;
			}
		}
	}
	if (res == 0) {
		d[u] = -1;
	}
	return res;
}
int Dinic() {
	int res = 0;
	while (bfs()) {
		res += dfs(S, 1e9);
	}
	return res;
}
vector<int> v;
bool vis[N];
void dfs_cut(int u) {
	vis[u] = 1;
	v.push_back(u);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (!vis[v] && e[i].c) {
			dfs_cut(v);
		}
	}
}
void min_cut() {
	dfs_cut(S);
	for (int i : v) {
		cout << i << ' ';
	}
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, f;
		cin >> u >> v >> f;
		adde(u, v, f);
	}
	cin >> S >> T;
	cout << Dinic() << '\n';
	min_cut();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

费用流

问题

给每条弧加上一个单位流量的费用，要求在最大流的基础上使得流量总和最小或最大。

分析

这里我们考虑基于EK实现，此时Dinic并不见得比EK更优。

算法思想：我们考虑给每条边加上一个边权，求解最短路的过程就变成求解最短或最长增广路，因为增广顺序对最大流并没有影响，我们发现这个过程可以在最大流的前提下求出最优代价，这个过程一般使用SPFA实现，其余步骤不变。

##实现

以最小费用最大流为例。

#include 
using namespace std;
const int N = 1005, M = 10005;
struct edge {
	int v, c, w, nxt;
} e[M];
int head[N], S, T, cnt;
inline void add(int u, int v, int c, int w) {
	e[cnt] = {v, c, w, head[u]}, head[u] = cnt++;
}
inline void adde(int u, int v, int c, int w) {
	add(u, v, c, w), add(v, u, 0, -w);	// 这里注意反向边要用负代价
}
bool vis[N];
int d[N], E[N];	// 这里注意E是基于最短路的
bool spfa() {	// 返回值：是否可以从S走到T
	memset(vis, 0, sizeof vis);
	memset(d, 0x3f, sizeof d);
	memset(E, -1, sizeof E);
	d[S] = 0;
	vis[S] = 1;
	queue<int> q;
	q.push(S);
	while (q.size()) {
		int u = q.front(); q.pop();
		vis[u] = 0;
		for (int i = head[u]; ~i; i = e[i].nxt) {
			if (e[i].c) {
				int v = e[i].v;
				if (d[u] + e[i].w < d[v]) {
					d[v] = d[u] + e[i].w;
					E[v] = i;
					if (!vis[v]) {
						q.push(v);
						vis[v] = 1;
					}
				}
			}
		}
	}
	return E[T] != -1;
}
int costflow() {
	int res = 0;
	while (spfa()) {
		int del = 1e9;
		for (int i = T; i != S; i = e[E[i] ^ 1].v) {	// 为什么遍历的下一个是反向边呢，因为这里写的是v
			del = min(e[E[i]].c, del);
		}
		for (int i = T; i != S; i = e[E[i] ^ 1].v) {
			e[E[i]].c -= del;
			e[E[i] ^ 1].c += del;
			res += e[E[i]].w * del;
		}
	}
	return res;
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	memset(head, -1, sizeof head);
	int n, m;
	cin >> n >> m;
	while (m--) {
		int u, v, c, w;
		cin >> u >> v >> c >> w;
		adde(u, v, c, w);
	}
	cin >> S >> T;
	cout << costflow() << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

技巧：拆点

方法

我们有时会希望通过一个点的流量不超过一个定值$val$，那该怎么办呢？

考虑将点$u$拆成两个点$u^{\prime }$和$u^{\prime \prime }$，原图中连向$u$的弧连向$u^{\prime }$，从$u$连出的弧从$u^{\prime \prime }$连出，再从$u^{\prime }$向$u^{\prime \prime }$连一条容量为$val$的弧即可，相当于若流入$u^{\prime }$的流量$>val$，通过$u^{\prime }$连出的唯一的容量为$val$的弧时，就不合法了。

例题

题意：$n$个人，两种物品，分别有$m1$和$m2$种，每种一个，每个人能拿一个物品1和一个物品2，每个人对两种物品都分别有一个喜欢列表，问最多多少人能同时选到喜欢的物品1和喜欢的物品2。($1\le n,m1,m2\le 100$)

我们考虑以$S\to 物1\to 人\to 物2\to T$的方式建立网络，所有弧容量均为$1$。

但是此时明显可能有一个人选多个物的情况，对答案会造成影响。则我们可以按照上述方法限制点流，将网络结构改成$S\to 物1\to {人}^{\prime }\to {人}^{\prime \prime }\to 物2\to T$，其中每个${人}^{\prime }$连向对应的${人}^{\prime \prime }$一条容量为$1$的弧，再跑最大流就好了。

#include 
using namespace std;
const int N = 105, M = 10005;
struct edge {
	int v, c, nxt;
} e[M];
int head[N], cnt;
inline void add(int u, int v, int c) {
	e[++cnt] = {v, c, head[u]}, head[u] = cnt;
}
inline void adde(int u, int v, int c) {
	add(u, v, c), add(v, u, 0);
}
int S, T, d[N];
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.push(S);
	d[S] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (d[v] == -1 && e[i].c) {
				d[v] = d[u] + 1;
				q.push(v);
			}
		}
	}
	return d[T] != -1;
}
int dfs(int u, int f) {
	if (u == T) {
		return f;
	}
	int res = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].c) {
			int t = dfs(v, min(f, e[i].c));
			e[i].c -= t;
			e[i ^ 1].c += t;
			res += t;
			f -= t;
			if (!f) {
				break;
			}
		}
	}
	return res;
}
int Dinic() {
	int res = 0;
	while (bfs()) {
		res += dfs(S, 1e9);
	}
	return res;
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m1, m2;
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= n; ++i) {
		adde(m1 + i, m1 + n + i, 1);	// 人' -> 人''
		int k1, k2, x;	// 两种物品个数
		cin >> k1 >> k2;
		while (k1--) {
			cin >> x;
			adde(x, m1 + i, 1);	// 物1 -> 人'
		}
		while (k2--) {
			cin >> x;
			adde(m1 + n + i, m1 + 2 * n + x, 1);	// 人'' -> 物2
		}
	}
	S = 0;
	T = m1 + m2 + 2 * n + 1;
	for (int i = 1; i <= m1; ++i) {
		adde(S, i, 1);	// S -> 物1
	}
	for (int i = 1; i <= m2; ++i) {
		adde(m1 + 2 * n + i, T, 1);	 // 物2 -> T
	}
	cout << Dinic() << '\n';
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

应用：混合图欧拉回路

问题

混合图，即有向边和无向边都有的图；欧拉路径，即一笔画最终回到起点。

分析

回顾一下之前有向图的结论：若图中每个点的入度和出度均相等，图中存在欧拉回路。

然鹅，对于混合图中的无向边，我们不知道其方向，我们的主要难点就是给其定向。

考虑随机定向再改方向，设随机定向后第$i$个点的入度为$in{d}_i$，出度为$out{d}_i$，则显然可以把所有点分为三类：

1. $in{d}_i>out{d}_i$；
2. $in{d}_i<out{d}_i$；
3. $in{d}_i==out{d}_i$。

第三类显然不用管。对于第一类，我们需要把$\frac{in{d}_i-out{d}_i}{2}$条指向$i$的边翻转，第二类同理，则若存在$|in{d}_i-out{d}_i|\mathrm{mod}2==1$个点，必然不存在欧拉回路，然后考虑网络流。

建立源点$S$和汇点$T$。

• 对于所有$in{d}_i>out{d}_i$，从$S$向$i$连一条容量为$\frac{in{d}_i-out{d}_i}{2}$的弧；
• 对于所有$in{d}_i<out{d}_i$，从$i$向$T$连一条容量为$\frac{out{d}_i-in{d}_i}{2}$的弧；
• 原图中的有向边因为方向固定，不用管；
• 对于随机定向的弧$<u,v>$，从$v$向$u$连一条容量为$1$的弧。

这里容量的含义想必大家已经懂了，就是最多能改方向的弧的条数。那么，当从$S$发出的弧均为满流，即$f_{max}={\sum }_{in{d}_i>out{d}_i}\frac{in{d}_i-out{d}_i}{2}$时，也就是所有需要改方向的弧都改了，存在欧拉回路，欧拉回路即为在随机定向的基础上将最大流中流量为$1$的弧反过来后的图。

实现

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 105, M = 10005;
struct edge {
	int v, c, nxt;
} e[M];
int head[N], cnt;
inline void add(int u, int v, int c) {
	e[++cnt] = {v, c, head[u]}, head[u] = cnt;
}
inline void adde(int u, int v, int c) {
	add(u, v, c), add(v, u, 0);
}
int S, T, d[N];
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.push(S);
	d[S] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (d[v] == -1 && e[i].c) {
				q.push(v);
				d[v] = d[u] + 1;
			}
		}
	}
	return d[T] != -1;
}
int dfs(int u, int f) {
	if (u == T) {
		return f;
	}
	int res = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].c) {
			int t = dfs(v, min(f, e[i].c));
			e[i].c -= t;
			e[i ^ 1].c += t;
			res += t;
			f -= t;
			if (!f) {
				break;
			}
		}
	}
	if (!res) {
		d[u] = -1;
	}
	return res;
}
int Dinic() {
	int res = 0;
	while (bfs()) {
		res += dfs(S, 1e9);
	}
	return res;
}
int ind[N], outd[N];
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	while (--m) {
		int u, v, op;	// 这里 op == 0 表示无向边，op == 1表示有向边
		cin >> u >> v >> op;
		if (!op) {
			adde(v, u, 1);
		}
	}
	S = 0, T = n + 1;
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		int k = ind[i] - outd[i];
		if (k % 2 == 0) {
			if (k) {
				adde(S, i, k / 2);
				sum += k / 2;
			} else {
				adde(i, T, -k / 2);
			}
		} else {
			cout << "No\n";
			return 0;
		}
	}
	cout << (Dinic() == sum ? "Yes\n" : "No\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

应用：最大权闭合图

问题

给定一个无边权但有点权的有向图，求其点权和最大且其中所有点的所有出边都指向其中点的子图。

分析

建立源点$S$和汇点$T$，将原图中边替换成容量为$\infty$的弧，从$S$向所有正权点连一条容量为其权值的弧，从所有负权点向$T$连一条容量为其权值绝对值的弧，此时的最大权闭合图的权值为所有正权点权值和减去最小割容量，具体子图即为在在网络中dfs，在流量不为$0$的情况下能到达点的集合。

实现

#include 
using namespace std;
const int N = 1e3 + 5, M = 1e5 + 5;
struct edge {
	int v, c, nxt;
} e[M];
int head[N], cnt;
inline void add(int u, int v, int c) {
	e[++cnt] = {v, c, head[u]}, head[u] = cnt;
}
inline void adde(int u, int v, int c) {
	add(u, v, c), add(v, u, 0);
}
int S, T, d[N];
bool bfs() {
	memset(d, -1, sizeof d);
	queue<int> q;
	q.push(S);
	d[S] = 0;
	while (q.size()) {
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			if (d[v] == -1 && e[i].c) {
				q.push(v);
				d[v] = d[u] + 1;
			}
		}
	}
	return d[T] != -1;
}
int dfs(int u, int f) {
	if (u == T) {
		return f;
	}
	int res = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].c) {
			int t = dfs(v, min(f, e[i].c));
			e[i].c -= t;
			e[i ^ 1].c += t;
			res += t;
			f -= t;
			if (!f) {
				break;
			}
		}
	}
	if (!res) {
		d[u] = -1;
	}
	return res;
}
int Dinic() {
	int res = 0;
	while (bfs()) {
		res += dfs(S, 1e9);
	}
	return res;
}
bool vis[N];
void dfs1(int u) {
	vis[u] = 1;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if (!vis[v] && e[i].c)  {
			dfs1(v);
		}
	}
}
int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, sum = 0;
	cin >> n >> m;
	S = 0, T = n + 1;
	for (int i = 1; i <= n; ++i) {
		int w;
		cin >> w;
		if (w == 0) {
			continue;
		}
		if (w) {
			adde(S, i, w);
			sum += w;
		} else {
			adde(i, T, -w);
		}
	}
	while (m--) {
		int u, v;
		cin >> u >> v;
		adde(u, v, 1e9);
	}
	cout << sum - Dinic() << '\n';
	dfs1(S);
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) {
			cout << i << ' ';
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

习题

[NOI2012] 美食节

题意

$n$种菜，每种菜$p_i$个，$m$个厨师，第$i$个厨师做第$j$道菜用时$t_{i,j}$，一道菜的等待时间为开始做到做完这道菜的用时，求所有菜的最小等待时间和。

分析

考虑费用流，要建立以下几种点：

• 源点$S$和汇点$T$；
• 每道菜；
• 第$i$和厨师做倒数第$j$道菜。

连以下几种边：

• $S$到每道菜，容量为$p_i$，费用为$0$；
• 厨师做菜的状态到$T$，容量为$1$，费用为$0$；
• 第$i$道菜到第$j$个厨师做倒数第$k$道菜的状态，容量为$1$，费用为$t_{i,j}\times k$，表示第$i$道菜就是第$j$个厨师做的倒数第$k$道，则剩下$k$道菜都要等$t_{i,j}$的时间。

这样连边发现边数很多，费用流明显会超时。

观察可发现，对于同样的第$i$道菜和第$j$个厨师，做菜的顺序肯定越靠后越好，后面没处理过的话绝对不会用到前面的，则先与$k=1$的状态连边，用到了再连就好。

洛谷P1361 小M的作物

题意

$n$个种子，$A,B$两个耕地，每个种子只能放在其中一个耕地中，各有一定收益，一些组合放在同一个耕地中会有额外收益，求收益最大值。

分析

先不考虑额外收益，则方案为：

• 建立点$A$和$B$，每个种子建点；
• 从$A$向每个种子连容量为这个种子放到耕地$A$里的收益的弧，种子向$B$连的同理；
• 因为一个种子不能同时放到$A$和$B$，还要求收益最大，则考虑最小割，剩下部分即为答案。

对于组合，我们建立一个点$u$，代表将这个组合放到$A$里的方案，$v$代表放到$B$里的方案，向组合中每个点连容量为$\infty$的弧，因为不能割，再从$S$向$u$连容量为放到$A$里收益的弧，从$v$向$T$连容量为放到$B$里收益的弧即可。

这次关于网络流的学习就到这里，感谢收看。