最小割
概念
割
对于一个网络流图 𝐺 =(𝑉,𝐸)
,其割的定义为一种 点的划分方式:将所有的点划分为 𝑆
和 𝑇 =𝑉 −𝑆
两个集合,其中源点 𝑠 ∈𝑆
,汇点 𝑡 ∈𝑇
。
割的容量
我们的定义割 (𝑆,𝑇)
的容量 𝑐(𝑆,𝑇)
表示所有从 𝑆
到 𝑇
的边的容量之和,即 𝑐(𝑆,𝑇) =∑𝑢∈𝑆,𝑣∈𝑇𝑐(𝑢,𝑣)
。当然我们也可以用 𝑐(𝑠,𝑡)
表示 𝑐(𝑆,𝑇)
。
最小割
最小割就是求得一个割 (𝑆,𝑇)
使得割的容量 𝑐(𝑆,𝑇)
最小。
证明
最大流最小割定理
参见 最大流 页面最大流最小割定理一节。
代码
最小割
通过 最大流最小割定理,我们可以直接得到如下代码:
参考代码
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 | #include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
constexpr int N = 1e4 + 5, M = 2e5 + 5;
int n, m, s, t, tot = 1, lnk[N], ter[M], nxt[M], val[M], dep[N], cur[N];
void add(int u, int v, int w) {
ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, val[tot] = w;
}
void addedge(int u, int v, int w) { add(u, v, w), add(v, u, 0); }
int bfs(int s, int t) {
memset(dep, 0, sizeof(dep));
memcpy(cur, lnk, sizeof(lnk));
std::queue<int> q;
q.push(s), dep[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (val[i] && !dep[v]) q.push(v), dep[v] = dep[u] + 1;
}
}
return dep[t];
}
int dfs(int u, int t, int flow) {
if (u == t) return flow;
int ans = 0;
for (int &i = cur[u]; i && ans < flow; i = nxt[i]) {
int v = ter[i];
if (val[i] && dep[v] == dep[u] + 1) {
int x = dfs(v, t, std::min(val[i], flow - ans));
if (x) val[i] -= x, val[i ^ 1] += x, ans += x;
}
}
if (ans < flow) dep[u] = -1;
return ans;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
int x;
while ((x = dfs(s, t, 1 << 30))) ans += x;
}
return ans;
}
int main() {
scanf("%d%d%d%d", &n, &m, &s, &t);
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
addedge(u, v, w);
}
printf("%d\n", dinic(s, t));
return 0;
}
|
方案
我们可以通过从源点 𝑠
开始 DFS,每次走残量大于 0
的边,找到所有 𝑆
点集内的点。
| void dfs(int u) {
vis[u] = 1;
for (int i = lnk[u]; i; i = nxt[i]) {
int v = ter[i];
if (!vis[v] && val[i]) dfs(v);
}
}
|
割边数量
如果需要在最小割的前提下最小化割边数量,那么先求出最小割,把没有满流的边容量改成 ∞
,满流的边容量改成 1
,重新跑一遍最小割就可求出最小割边数量;如果没有最小割的前提,直接把所有边的容量设成 1
,求一遍最小割就好了。
问题模型 1
有 𝑛
个物品和两个集合 𝐴,𝐵
,如果一个物品没有放入 𝐴
集合会花费 𝑎𝑖
,没有放入 𝐵
集合会花费 𝑏𝑖
;还有若干个形如 𝑢𝑖,𝑣𝑖,𝑤𝑖
限制条件,表示如果 𝑢𝑖
和 𝑣𝑖
同时不在一个集合会花费 𝑤𝑖
。每个物品必须且只能属于一个集合,求最小的代价。
这是一个经典的 二者选其一 的最小割题目。我们对于每个集合设置源点 𝑠
和汇点 𝑡
,第 𝑖
个点由 𝑠
连一条容量为 𝑎𝑖
的边、向 𝑡
连一条容量为 𝑏𝑖
的边。对于限制条件 𝑢,𝑣,𝑤
,我们在 𝑢,𝑣
之间连容量为 𝑤
的双向边。
注意到当源点和汇点不相连时,代表这些点都选择了其中一个集合。如果将连向 𝑠
或 𝑡
的边割开,表示不放在 𝐴
或 𝐵
集合,如果把物品之间的边割开,表示这两个物品不放在同一个集合。
最小割就是最小花费。
问题模型 2
最大权值闭合图,即给定一张有向图,每个点都有一个权值(可以为正或负或 0
),你需要选择一个权值和最大的子图,使得子图中每个点的后继都在子图中。
做法:建立超级源点 𝑠
和超级汇点 𝑡
,若节点 𝑢
权值为正,则 𝑠
向 𝑢
连一条有向边,边权即为该点点权;若节点 𝑢
权值为负,则由 𝑢
向 𝑡
连一条有向边,边权即为该点点权的相反数。原图上所有边权改为 ∞
。跑网络最大流,将所有正权值之和减去最大流,即为答案。
几个小结论来证明:
- 每一个符合条件的子图都对应流量网络中的一个割。因为每一个割将网络分为两部分,与 𝑠
相连的那部分满足没有边指向另一部分,于是满足上述条件。这个命题是充要的。 - 最小割所去除的边必须与 𝑠
和 𝑡
其中一者相连。因为否则边权是 ∞
,不可能成为最小割。 - 我们所选择的那部分子图,权值和 =
所有正权值之和 −
我们未选择的正权值点的权值之和 +
我们选择的负权值点的权值之和。当我们不选择一个正权值点时,其与 𝑠
的连边会被断开;当我们选择一个负权值点时,其与 𝑡
的连边会被断开。断开的边的边权之和即为割的容量。于是上述式子转化为:权值和 =
所有正权值之和 −
割的容量。 - 于是得出结论,最大权值和 =
所有正权值之和 −
最小割 =
所有正权值之和 −
最大流。
习题
本页面最近更新:2024/10/9 22:38:42,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Ir1d, MegaOwIer, Enter-tainer, Henry-ZHR, ksyx, ouuan, Tiphereth-A, Xeonacid, diauweb, huaruoji, ImpleLee, laocongsc, LuoYisu, Lynricsy, NachtgeistW, Nanarikom, Siyuan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用