【网络流】总结

技术分享 3年前 (2023-08-14) 0 999+

关注

一、定义

设 (u) 和 (v) 为一张图上的任意两个节点。令 (c(u, v)) 为它们之间的边的容量， (f(u, v)) 为它们之间的流量，则需要满足以下限制。

容量限制：对于每条边，都必须满足 (f(u, v) leq c(u, v)) 。
斜对称性：对于每条边，其流量与其相反边的容量互为相反数，即 (f(u, v) = -f(v, u)) 。
流守恒性：从源点流出的流量等于流入汇点的流量。

对于网络上的任意一点 (x) ，流入该节点的流量一定等于流出该节点的容量。特别地，源点 (s) 的流入量为 0，汇点 (t) 的流出量为 0，当然，源点的流出量一定等于汇点的流入量。

整张网络的流定义为从源点流出的流量总和。

有关于网络流的常见问题有 4 种：

最大流。
最小割。
费用流。
上下界网络流。

接下来一一介绍一下。

二、最大流

故名思意：整张网络的最大流。

我们定义增广路为：若从 (s) 到 (t) 的一条路径中，边的所有剩余容量均大于 0，则称这样的一条路径为增广路。

在这里简单介绍两种常用的最大流算法。

1、EK 算法

~~全名忘了。~~

显然，如果图中存在增广路，我们可以让一股流量沿着这条增广路从源点流到汇点。

那么 EK 算法的核心便是：利用 bfs 不断地在网络中寻找出增广路，直到网络中不存在一条增广路为止。

而每一次只要找到一条增广路，就更新路径上每一条边的剩余容量。同时网络的最大流量也会改变。

但值得注意的是，如果增广路上的流为 (delta) ，每一次我们不仅要将路径上所有正向边的剩余容量减去 (delta) ，还要将所有正向边所对应的反向边的剩余容量加上 (delta) 。

为什么？

这就不得不提起反向边的概念了。

反向边

为什么要有这个东西？

这是因为每一条边不一定只在一条增广路中出现，它可能被多条增广路同时包含。

为了寻找出所有增广路，我们要让所有的边有被二次筛选的机会。

而反向边给了它们这个机会。你可以感性地理解为，反向边给了程序一个反悔的机会。

为什么要反悔？

如果找到增广路后直接进行更改，则会影响后续继续寻找增广路，因此产生了反向边。

注意：反向边的初始容量为 0，而且反向边的当前容量其实也可以直接代表这条边的当前流量。

以网络最大流为模板给个代码吧。

Code:

#include<bits/stdc++.h> using namespace std; #define SF scanf #define PF printf #define int long long struct Edge { 	int to, next, w; }edge[100005]; int head[10005], cnt = 1, a[1005][1005], aug[1005], pre[1005], ans, s, t; bool vis[10005]; void add(int u, int v, int w) { 	edge[++cnt].to = v; 	edge[cnt].next = head[u]; 	edge[cnt].w = w; 	head[u] = cnt; } int bfs(int x) { 	queue<int> q; 	q.push(x); 	memset(vis, 0, sizeof(vis)); 	vis[x] = 1; 	aug[x] = INT_MAX; 	while(!q.empty()) { 		int tmp = q.front(); 		q.pop(); 		for(int i = head[tmp]; i; i = edge[i].next) { 			int to = edge[i].to; 			if(vis[to] || edge[i].w <= 0) continue; 			vis[to] = 1; 			pre[to] = i; 			q.push(to); 			aug[to] = min(edge[i].w, aug[tmp]); 			if(to == t) return 1; 		} 	} 	return 0; } void change() { 	int now = t; 	while(now != s) { 		int k = pre[now]; 		edge[k].w -= aug[t]; 		edge[k ^ 1].w += aug[t]; 		now = edge[k ^ 1].to; 	} 	ans += aug[t]; } signed main() { 	int n, m; 	SF("%lld%lld%lld%lld", &n, &m, &s, &t); 	for(int i = 1; i <= m; i++) { 		int u, v, w; 		SF("%lld%lld%lld", &u, &v, &w); 		if(a[u][v] == 0) { 			add(u, v, w), add(v, u, 0); 			a[u][v] = cnt; 		} 		else edge[a[u][v] - 1].w += w; 	} 	while(bfs(s) != 0) change(); 	PF("%lld", ans); 	return 0; }

2、dinic算法

~~或许这就是它的全名？~~

想一想为什么 EK 的效率不如 dinic。

因为 EK 算法找到一条增广路就迫不及待地进行了更新。

那么 dinic 就在它的基础上一次性寻找了多条增广路，再统一进行更新。

如何实现？

对于一个节点 (x) ，设 (d_x) 表示它的层级。即从 (s) 到 (x) 最少经过的边的数量。再设 (x) 连接的下一个节点为 (y) ，如果它们间的 (c(x, y) > 0) （即还有剩余容量）时，令 (d_y = d_x + 1) 。

再用 (dfs) 逐层遍历。从 (s) 开始向下一层寻找合法的节点（即满足上述关系式），直到找到 (t) ，再回溯上来。这样不就一次性寻找并修改了多条增广路的边的容量了吗？

当前弧优化

一句话解释，从上一次结束搜索的那条边继续进行搜索。

~~我认为还是比较容易理解的。~~

还是以上述模板题目为例给一份代码：

Code:

#include<bits/stdc++.h> using namespace std; #define SF scanf #define PF printf #define int long long struct Edge { 	int to, next, w; }edge[200005]; int head[200005], cnt = 1, d[200005], now[200005]; //now数组就是当前弧优化的数组 void add(int u, int v, int w) { 	edge[++cnt].to = v; 	edge[cnt].next = head[u]; 	edge[cnt].w = w; 	head[u] = cnt; } bool bfs(int s, int t) { 	queue<int> q; 	q.push(s); 	memset(d, 0, sizeof(d)); 	d[s] = 1, now[s] = head[s]; 	while(!q.empty()) { 		int tmp = q.front(); 		q.pop(); 		for(int i = head[tmp]; i; i = edge[i].next) { 			int to = edge[i].to; 			if(d[to] || edge[i].w <= 0) continue; 			d[to] = d[tmp] + 1; 			now[to] = head[to]; 			q.push(to); 			if(to == t) return true; 		} 	} 	return false; } int dinic(int x, int t, int flow) { 	if(x == t) return flow; 	int rest = flow; 	for(int i = now[x]; i && rest; i = edge[i].next) { 		int to = edge[i].to; 		now[x] = i; 		if(d[to] != d[x] + 1 || edge[i].w <= 0) continue; 		int k = dinic(to, t, min(rest, edge[i].w)); 		if(k == 0) d[to] = 0; 		edge[i].w -= k; 		edge[i ^ 1].w += k; 		rest -= k; 	} 	return flow - rest; } int work(int s, int t) { 	int ans = 0, delta; 	while(bfs(s, t)) { 		while(delta = dinic(s, t, INT_MAX)) ans += delta; 	} 	return ans; } signed main() { 	int n, m, s, t; 	SF("%lld%lld%d%lld", &n, &m, &s, &t); 	for(int i = 1; i <= m; i++) { 		int u, v, w; 		SF("%lld%lld%lld", &u, &v, &w); 		add(u, v, w), add(v, u, 0); 	} 	PF("%lld", work(s, t)); 	return 0; }

三、最小割

1、定义

把一张网络中的所有点分为 2 个点集，设其为 (S) 和 (T) ，其中源点 (s in S) ， (t in T) 。但需满足以下两点。

(S) 和 (T) 的交集为空集。
(S) 和 (T) 的并集为完整点集。

显然，要满足上面两个条件，我们一定要割掉一些边。

我们就将割掉的边的最小权值和叫做最小割。

怎么求呢？

结论：最小割的值等于最大流的值。

怎么证呢？

~~这不是显然吗，~~这里不再详细证明了，毕竟这玩意儿有点东西。~~自己去问度娘。~~

Code:

去上面看吧。

四、费用流

1、定义

在网络中的每条边上加上费用，设其为 (w(u, v)) 。则每次经过 (u) 和 (v) 之间的边时，需要付出 (w(u, v)) 的费用。

从源点 (s) 到汇点 (t) 因流过的量所付出的费用称为费用流。

2、解法

利用~~已壮烈牺牲多年的同志~~ SPFA 来求解。

为什么要用这玩意儿而不用复杂度更加稳定的 Dijkstra 呢？

因为图中有可能存在负环。

当然，存在负环时也是可以跑网络流的，只不过需要涉及到消圈算法，这里先不考虑。

首先我们要把费用当成权值跑一遍 SPFA，拿到到达每个点 (i) 的最少费用，设其为 (dis_i)。

这里就有一个好处：(dis) 数组已经帮助我们分好层了。

因此接下来跑一遍 dinic 就 OK 了。

代码改动不大，这里就先不贴了。

五、上下界网络流

最大流只是限制了边的上界，要是同时限制了下界怎么办呢？

1、无源汇上下界可行流

很好理解：没有源点和汇点，但网络中有上下界限制时的一个可行的流。

既然没有源汇点，也就没有最大流一说了。

我们要求的是每条边的流量，使得整张网络平衡，或是报告无解。

建议在读下面的内容时自己拿笔画一画。以便于理解。

首先我们建立一张只有下界的网络，图中所有边都是满流状态。

这张网络很有可能不平衡。

因此我们再建立一张差网络，容量即为上界减去下界之差。

在下界网络中，有点 (i) ，设流入它的点的量为 (in_i) ，流出它的点的量为 (out_i) 。分为 2 种情况考虑。

如果 (in_i > out_i) ，那我们希望在差网络中从 (i) 点流出的量比流入多 (in_i - out_i) 的量。因此考虑从源点 (s) 向 (i) 点连容量为 (in_i - out_i) 的边。
如果 (out_i > in_i) ，那我们希望在差网络中流入 (i) 点的量比流出的多 (out_i - in_i) 的量。因此考虑从 (i) 点向汇点 (t) 连容量为 (out_i - in_i) 的边。

最后在差网络上跑出最大流，得到每条边的流量，再加上下界网络的流，就可以得到一个可行流了。

肯定有无解的情况。

显然，如果一条边的一端是源点 (s) 或是汇点 (t) 时，这条边必须满流来维护下界网络的平衡。所以只要这些边中有一条边不满流，则报告无解。

但是在实际操作中，我们并不需要真正地建立下界网络。它的唯一一个作用就是帮助我们得到 (in_i) 和 (out_i) ，显然我们在输入过程中就可以得到。

以无源汇上下界可行流为模板给个代码吧。

Code:

#include<bits/stdc++.h> using namespace std; #define SF scanf #define PF printf struct Edge { 	int to, next, w; }edge[200005]; int u[200005], v[200005], in[2000005], out[200005], head[200005], d[200005], now[200005], Min[200005], cnt = 1; bool vis[200005]; void add(int u, int v, int w) { 	edge[++cnt].to = v; 	edge[cnt].next = head[u]; 	edge[cnt].w = w; 	head[u] = cnt; } bool bfs(int s, int t) { 	queue<int> q; 	q.push(s); 	memset(d, 0, sizeof(d)); 	d[s] = 1, now[s] = head[s]; 	while(!q.empty()) { 		int tmp = q.front(); 		q.pop(); 		for(int i = head[tmp]; i; i = edge[i].next) { 			int to = edge[i].to; 			if(d[to] || edge[i].w <= 0) continue; 			d[to] = d[tmp] + 1; 			now[to] = head[to]; 			q.push(to); 			if(to == t) return true; 		} 	} 	return false; } int dinic(int x, int t, int flow) { 	if(x == t) return flow; 	int rest = flow, i; 	for(i = now[x]; i && rest; i = edge[i].next) { 		int to = edge[i].to; 		if(d[to] != d[x] + 1 || edge[i].w <= 0) continue; 		int k = dinic(to, t, min(rest, edge[i].w)); 		if(k == 0) d[to] = 0; 		edge[i].w -= k; 		edge[i ^ 1].w += k; 		rest -= k; 	} 	now[x] = i; 	return flow - rest; } int work(int s, int t) { 	int ans = 0, delta; 	while(bfs(s, t)) { 		while(delta = dinic(s, t, INT_MAX)) ans += delta; 	} 	return ans; } int main() { 	int n, m, sum = 0; 	SF("%d%d", &n, &m); 	int s = 0, t = n + 1; 	for(int i = 1; i <= m; i++) { 		int Max; 		SF("%d%d%d%d", &u[i], &v[i], &Min[i], &Max); 		out[u[i]] += Min[i]; 		in[v[i]] += Min[i]; 		add(u[i], v[i], Max - Min[i]), add(v[i], u[i], 0); 	} 	for(int i = 1; i <= n; i++) { 		if(in[i] > out[i]) add(s, i, in[i] - out[i]), add(i, s, 0), sum += in[i] - out[i]; //记录必须要有多少流量从源点 s 流出 		else if(out[i] > in[i]) add(i, t, out[i] - in[i]), add(t, i, 0); 	} 	if(work(s, t) != sum) { //只要不是最大流，一定有边没有满流 		PF("NO"); 		return 0; 	} 	PF("YESn"); 	for(int i = 2; i <= 2 * m; i += 2) PF("%dn", Min[i / 2] + edge[i ^ 1].w); 	return 0; }

2、有源汇上下界可行流

很好理解：有源点和汇点，网络中有上下界限制时的一个可行流。

参照上题，先建立起下界网络和差网络。

可以从汇点 (t) 向源点 (s) 连一条下界为 0 ，容量无限大的边，就转换成了无源汇上下界可行流。

代码根本没啥改动。

遗憾的是，本题并没有找到模板题。

3、有源汇上下界最大流

很好理解：有源点和汇点，网络中有上下界限制时的一个最大流。

参照上题，先求出一个有源汇上下界可行流。

那么这个可行流的值是多少呢？

显然，整张网络的流量一定等于汇点 (t) 向源点 (s) 流入的量。设该值为 (index) 。

然后我们删去从 (t) 到 (s) 的边，再按照常规方法跑出从 (s) 到 (t) 的最大流 (MaxFlow) 。

最后的答案即为： (MaxFlow + index) 。

代码改动显然不大，不放了。

4、有源汇上下界最小流

很好理解：有源点和汇点，网络中有上下界限制时的一个最小流。

参照上题。

求出 (index) 后，跑出从 (t) 到 (s) 的最大流 (MaxFlow) 。

最后的答案即为：(index - MaxFlow) 。

总结

显然上面2、3、4条都是结论性的东西。证明起来有些晦涩。~~可能也没太大必要？~~因此就先放结论。以后有机会再来详细聊聊。~~说真的，上下界网络流考的不太多。~~现阶段就先记结论吧。

六、例题

1、奶牛食品

传送门

Algorithm：最大流。

基本上算是最大流的板子题。

介绍一种重要思路：拆点。

拆点

我们要明白拆点的意义究竟何在？

其实拆点就是将点权转化为边权。

拿此题讲，每只奶牛的贡献最多为 1。但它喜欢的食品和饮料不止 1 种。

如果直接用食品连接奶牛，奶牛连接饮料的话，它造成的贡献可能就不为 1 了。

因此，我们应该将奶牛 (i) 拆成 (i_x) 和 (i_y) 。一个用来表示是否得到喜欢的食品，另一个则表示是否得到喜欢的饮料。

做法显然了，超级源点 (s) 向第 (f) 个食品连接容量为 1 的边，第 (d) 个饮料向超级汇点 (t) 连接容量为 1 的边。

如果第 (i) 只奶牛喜欢第 (f) 个食品，就从 (f) 向 (i_x) 连一条容量为 1 的边。

如果第 (i) 只奶牛喜欢第 (d) 个饮料，就从 (i_y) 向 (d) 连一条容量为 1 的边。

当然，每个 (i_x) 也要向 (i_y) 连一条容量为 1 的边。上面说过每只奶牛的贡献最多为 1，因此容量为 1。

建图Code:

/* 第i个点：i -> max = n  第i个吃: n + i -> max = n + lena 第i个喝：n + lena + i -> max = n + lena + lenb 第i个虚点： n + lena + lenb + i -> max = n + lena + lenb + n  */ int s = 0, t = 2 * n + lena + lenb + 1; for(int i = 1; i <= n; i++) { 	int len1, len2, x; 	SF("%d%d", &len1, &len2); 	for(int j = 1; j <= len1; j++) { 		SF("%d", &x); 		add(n + x, i, 1), add(i, n + x, 0);		 	} 	for(int j = 1; j <= len2; j++) { 		SF("%d", &x); 		add(n + lena + lenb + i, n + lena + x, 1), add(n + lena + x, n + lena + lenb + i, 0); 	} 	add(i, n + lena + lenb + i, 1), add(n + lena + lenb + i, i, 0); } for(int i = 1; i <= lena; i++) add(s, n + i, 1), add(n + i, s, 0); for(int i = 1; i <= lenb; i++) add(n + lena + i, t, 1), add(t, n + lena + i, 0);

2、猪

传送门

Algorithm：最大流。

有难度。

设第 (i) 个猪舍中有 (a_i) 头猪。

对每个猪舍 (x) 分类讨论。

该猪舍第一次被顾客 (i) 打开。

这时可以从源点 (s) 向 (i) 连一条容量为 (a_x) 的边。表示第 (i) 个顾客最多从该猪舍买走 (a_x) 头猪。
该猪舍在被顾客 (i) 打开前已经被打开过。

这时猪舍中的猪未知，怎么办呢？

我们设上一位打开该猪舍的顾客为 (last_x) 。

对 (last_x) 打开过的所有猪舍，我们都可以对里面的猪随意操作。

可以理解为，(last_x) 和 (i) 是好朋友，(last_x) 担心自己买完猪后 (i) 不够买了，于是把自己能买的猪都买了，在 (i) 来的时候送给他了。

所以我们从 (last_x) 向 (i) 连接一条容量为无限的边，表示 (last_x) 可以送给 (i) 无限多的猪以至于可满足 (i) 的需求。

这样一来，问题就解决了。

当然，如果顾客 (i) 计划买 (x_i) 头猪，就从 (i) 向汇点 (t) 连接一条容量为 (x_i) 的边。表示他买的猪的数量。

至此，本题结束。

建图Code:

s = 0, t = n + 1; for(int i = 1; i <= m; i++) SF("%d", &a[i]); for(int i = 1; i <= n; i++) { 	int len, x; 	SF("%d", &len); 	for(int j = 1; j <= len; j++) { 		SF("%d", &x); 		if(last[x] == 0) { 			last[x] = i; 			add(s, i, a[x]), add(i, s, 0); 		}   		else add(last[x], i, 0x3f3f3f3f), add(i, last[x], 0), last[x] = i; 	} 	SF("%d", &x); 	add(i, t, x), add(t, i, 0); }

3、蜥蜴

传送门

Algorithm：最大流。

思路倒不难，调试起来有些困难。

在第一张图中，设第 (i) 行，第 (j) 列的石柱最多能够被跳 (w_{i, j}) 次。为了方便，赋予它一个编号 (k_{i, j}) 。

显然，根据上面拆点的思想，这里需要点权转边权。因此将第 (i) 行第 (j) 列的石柱拆为 (k_{i, j, x}) 和 (k_{i, j, y}) ，它们间边权即为 (w_{i, j}) 。

在第二张图中，如果第 (i) 行，第 (j) 列上有蜥蜴，就从源点 (s) 向 (k_{i, j, x}) 连接一条容量为 1 的边。再进一步，如果这只蜥蜴可以直接跳出图外，就从 (k_{i, j, y}) 向汇点 (t) 连接一条容量为 1 的边。

接下来枚举任意两块石柱。第一块在第 (i) 行，第 (j) 列，第二块在第 (l) 行，第 (r) 列。如果他们间的距离足以让蜥蜴跳过，就在 (k_{i, j, y}) 和 (k_{l, r, x}) 间连接一条容量为 1 的边，表示从第一块跳到第二块。同样，在 (k_{l, r, x}) 和 (k_{i, j, y}) 间连接一条容量为 1 的边，表示从第二块跳到第一块。

到这里，建图就结束了。

建图Code:

SF("%d%d%d", &n, &m, &Max); for(int i = 1; i <= n; i++) { 	for(int j = 1; j <= m; j++) { 		char c; 		cin >> c; 		if(c != '0') x[++len] = i, y[len] = j, w[len] = c - '0', k[i][j] = len; 	} } s = 0, t = 2 * len + 1; for(int i = 1; i <= n; i++) { 	for(int j = 1; j <= m; j++) { 		char c; 		cin >> c; 		if(c == 'L') { 			sum++; 			add(s, k[i][j], 1), add(k[i][j], s, 0); 		} 	} } for(int i = 1; i <= len; i++) { 	add(i, i + len, w[i]), add(i + len, i, 0); 	for(int j = i + 1; j <= len; j++) { 		if(get_dis(x[i], y[i], x[j], y[j]) <= Max * Max) add(i + len, j, 0x3f3f3f3f), add(j, i + len, 0), add(j + len, i, 0x3f3f3f3f), add(i, j + len, 0); 	} } for(int i = 1; i <= len; i++) { 	if(x[i] <= Max || y[i] <= Max || x[i] + Max > n || y[i] + Max > m) add(i + len, t, 0x3f3f3f3f), add(t, i + len, 0); }

4、有线电视网络

传送门

Algorithm：最小割

显然，割掉一个点，所有与这个点的相连的边都会一并被删掉。

所以将第 (i) 个点拆为 (i_x) 和 (i_y) 。

如果 (u) 和 (v) 之间有一条无向边，就从 (u_y) 向 (v_x) 间连一条容量为无限的边。同时也从 (v_y) 向 (u_x) 间连一条容量为无限的边。

为什么是无限？

因为题目中不让删边，容量设为无限那么最小割一定不会割掉它。

同时，对于任意一个非源点并且非汇点的点 (i) ，从 (i_x) 向 (i_y) 间连一条容量为 1 的边。表示删除该点需要 1 的代价。

为什么要排掉源汇点呢？

如果不排掉的话，最小割就可能会选择割掉 (s_x) 和 (s_y) 间的边或 (t_x) 和 (t_y) 间的边。此时满足最小割的定义，会直接返回。但实际上割掉源汇点后图可能还是联通的。

所以干脆就不割，将 (s_x) 和 (s_y) 间的边和 (t_x) 和 (t_y) 间的边的容量设为无限。

这样就需要枚举每个源汇点来去最小值才能保证正确性了。

难度不大，能够帮助我们进一步理解拆点的意义。

建图简单，输入很恶心，只给输入的代码。

建图Code:

for(int i = 1; i <= m; i++) { 	SF("%s", c + 1); 	int lenc = strlen(c + 1); 	bool flag = false; 	for(int j = 1; j <= lenc; j++) { 		int sum = 0, u, v; 		bool F = false; 		while(c[j] >= '0' && c[j] <= '9') { 			F = true; 			sum = (sum << 3) + (sum << 1) + (c[j] ^ 48); 			j++; 		} 		if(!F) continue; 		sum++; 		if(!flag) a[i] = sum, flag = true; 		else b[i] = sum; 	} }

5、狼和羊的故事

传送门

Algorithm：最小割

为了方便，将所有狼的坐标存储在 (id1) 里，羊的坐标存储在 (id2) 里，空点的坐标存储在 (id3) 里。它们都是 pair 类型的。

对于图中的第 (i) 行，第 (j) 列，赋予它一个编号 (num_{i, j})。

题目描述说空点不是任何一只动物的领地，其实意思是狼可以通过空点来进攻羊。

所以狼有两种方式进攻羊：

相邻的节点中就有羊，直接进攻。
相邻的节点中有空点，空点可以通过若干个空点与羊相邻，通过空点进攻。

因此该题建图的思路就出来了。

枚举第 (i) 只狼和第 (j) 个空点。如果它们间的曼哈顿距离为 1，则从 (num_{id1_i.first, id1_i.second}) 向 (num_{id3_j.first, id3_j.second}) 连接一条容量为 1 的边，表示第 (i) 只狼可以到达第 (j) 个空点。
枚举第 (i) 个空点和第 (j) 只羊。如果它们间的曼哈顿距离为 1，则从 (num_{id3_i.first, id3_i.second}) 向 (num_{id2_j.first, id2_j.second}) 连接一条容量为 1 的边，表示第 (i) 个空点可以到达第 (j) 只羊。
枚举任意两个空点 (i) 和 (j)。如果它们间的曼哈顿距离为 1，则从 (num_{id3_i.first, id3_i.second}) 向 (num_{id3_j.first, id3_j.second}) 连接一条容量为 1 的边，表示第 (i) 个空点可以到达第 (j) 个空点。
枚举第 (i) 只狼和第 (j) 只羊。如果它们间的曼哈顿距离为 1，则从 (num_{id1_i.first, id1_i.second}) 向 (num_{id2_j.first, id2_j.second}) 连接一条容量为 1 的边，表示在它们之间加一个单位距离的栅栏。

源点和汇点怎么处理呢？

枚举第 (i) 只狼，从源点 (s) 向它连一条容量为无限的边。

枚举第 (i) 只狼，从它向汇点 (t) 连一条容量为无限的边。

你不可能将任何一只狼或者任何一只羊莫名删掉，因此容量为无限。

跑一便最小割即可。

建图Code:

SF("%d%d", &n, &m); for(int i = 1; i <= n; i++) { 	for(int j = 1; j <= m; j++) { 		SF("%d", &x); 		num[i][j] = ++sum; 		if(x == 1) id1[++len1].first = i, id1[len1].second = j; 		else if(x == 2) id2[++len2].first = i, id2[len2].second = j; 		else id3[++len3].first = i, id3[len3].second = j; 	} } int S = 0, T = sum + 1; for(int i = 1; i <= len1; i++) add(S, num[id1[i].first][id1[i].second], 0x3f3f3f3f), add(num[id1[i].first][id1[i].second], S, 0); for(int i = 1; i <= len2; i++) add(num[id2[i].first][id2[i].second], T, 0x3f3f3f3f), add(T, num[id2[i].first][id2[i].second], 0); for(int i = 1; i <= len1; i++) { 	for(int j = 1; j <= len3; j++) { 		if(abs(id1[i].first - id3[j].first) + abs(id1[i].second - id3[j].second) == 1) add(num[id1[i].first][id1[i].second], num[id3[j].first][id3[j].second], 1), add(num[id3[j].first][id3[j].second], num[id1[i].first][id1[i].second], 0); 	} } for(int i = 1; i <= len3; i++) { 	for(int j = 1; j <= len2; j++) { 		if(abs(id3[i].first - id2[j].first) + abs(id3[i].second - id2[j].second) == 1) add(num[id3[i].first][id3[i].second], num[id2[j].first][id2[j].second], 1), add(num[id2[j].first][id2[j].second], num[id3[i].first][id3[i].second], 0); 	} } for(int i = 1; i <= len3; i++) { 	for(int j = 1; j <= len3; j++) { 		if(i == j) continue; 		if(abs(id3[i].first - id3[j].first) + abs(id3[i].second - id3[j].second) == 1) add(num[id3[i].first][id3[i].second], num[id3[j].first][id3[j].second], 1), add(num[id3[j].first][id3[j].second], num[id3[i].first][id3[i].second], 0); 	} } for(int i = 1; i <= len1; i++) { 	for(int j = 1; j <= len2; j++) { 		if(abs(id1[i].first - id2[j].first) + abs(id1[i].second - id2[j].second) == 1) add(num[id1[i].first][id1[i].second], num[id2[j].first][id2[j].second], 1), add(num[id2[j].first][id2[j].second], num[id1[i].first][id1[i].second], 0); 	} }

6、航空路线问题

传送门

Algorithm：费用流

初看此题似乎看不出来得用费用流。没关系，我们先站在最大流的角度思考一下问题。

需要我们找到 2 条路线：一条要从 (s) 到 (t) ，另一条要从 (t) 到 (s) ，并且往返途中每座城市只能经过一次。不难想到拆点。对于点 (i) ，拆成入点 (in_i) 和出点 (out_i) 。从 (in_i) 向 (out_i) 连接一条容量为 1 的边，表示该点最多经过一次。特别地，(in_s) 和 (out_s) 之间的容量为 2，(in_t) 和 (out_t) 之间的容量也为 2。对于两个点 (u) 和 (v) ，如果它们之间有路径，则从 (out_u) 向 (in_v) 连接一条容量为无限的边。

做题经验告诉我们，此题可以转化成从 (s) 到 (t) 找到 2 条不同的路径，再输出答案即可。

当然，如果最大流不为 2，说明 (s) 和 (t) 不连通，输出无解。

至此，本题结束。了吗？

事实告诉我们，如果单单只跑最大流并判断无解，只能拿到 (27pts) ，为什么会错呢？

因为我们要保证路过的城市尽可能多，而不是仅仅找出 2 条路径。

这就是此题需要费用流的原因。

对于每一个点 (i) ，在 (in_i) 和 (out_i) 之间的边上加上 1 点费用，表示流经了一座城市。其它的所有边费用均为 0，再跑一遍最大费用最大流就解决了此题。

补：将所有城市的名字用 (map) 映射成数字后比较好处理。

建图Code:

S = 0, T = 2 * n + 1; for(int i = 1; i <= n; i++) { 	cin >> u; 	mp[u] = ++_, Mp[_] = u; //map映射 	if(i == 1) add(S, mp[u], 2, 0), add(mp[u], S, 0, 0), add(mp[u], mp[u] + n, 2, -1), add(mp[u] + n, mp[u], 0, 1); 	else if(i == n) add(mp[u], T, 2, 0), add(T, mp[u], 0, 0), add(mp[u], mp[u] + n, 2, -1), add(mp[u] + n, mp[u], 0, 1); 	else add(mp[u], mp[u] + n, 1, -1), add(mp[u] + n, mp[u], 0, 1); } //将每个费用取反后跑最小费用，跑出来的答案取反就是最大费用了 for(int i = 1; i <= m; i++) { 	cin >> u >> v; 	add(mp[u] + n, mp[v], 0x3f3f3f3f, 0), add(mp[v], mp[u] + n, 0, 0); }

给一下我习惯用的拉答案的方式供参考：

void get_res(int x) { 	if(x == T) return; 	res[len][++res[len][0]] = (x > n ? x - n : x); 	for(int i = head[x]; i; i = edge[i].next) { 		int to = edge[i].to; 		if(i & 1) continue; //链式前向星的性质 		if(edge[i ^ 1].c) { 			edge[i ^ 1].c--; 			get_res(to); 			break; 		} 	} } -----------------------------------------分割线------------------------------------------- for(int i = head[S]; i; i = edge[i].next) { 	if(i & 1) continue;  	while(edge[i ^ 1].c) { 		edge[i ^ 1].c--; 		len++; 		get_res(edge[i].to); 	} } int len1 = unique(res[0] + 1, res[0] + 1 + res[0][0]) - res[0] - 1; int len2 = unique(res[1] + 1, res[1] + 1 + res[1][0]) - res[1] - 1; cout << len1 + len2 - 2 << endl; for(int i = 1; i < len1; i++) cout << Mp[res[0][i]] << endl; for(int i = len2; i; i--) cout << Mp[res[1][i]] << endl;

这种方式每次只能拉 1 点流量，较为耗时，但已经足以面对绝大多数情况了。