跳转至

最小割

概念

割

對於一個網絡流圖 \(G=(V,E)\)，其割的定義為一種 點的劃分方式：將所有的點劃分為 \(S\) 和 \(T=V-S\) 兩個集合，其中源點 \(s\in S\)，匯點 \(t\in T\)。

割的容量

我們的定義割 \((S,T)\) 的容量 \(c(S,T)\) 表示所有從 \(S\) 到 \(T\) 的邊的容量之和，即 \(c(S,T)=\sum_{u\in S,v\in T}c(u,v)\)。當然我們也可以用 \(c(s,t)\) 表示 \(c(S,T)\)。

最小割

最小割就是求得一個割 \((S,T)\) 使得割的容量 \(c(S,T)\) 最小。

證明

最大流最小割定理

參見 最大流 頁面最大流最小割定理一節。

代碼

最小割

通過 最大流最小割定理，我們可以直接得到如下代碼：

參考代碼 
 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>

const 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;
}

方案

我們可以通過從源點 \(s\) 開始 DFS，每次走殘量大於 \(0\) 的邊，找到所有 \(S\) 點集內的點。

1
2
3
4
5
6
7
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);
  }
}

割邊數量

如果需要在最小割的前提下最小化割邊數量，那麼先求出最小割，把沒有滿流的邊容量改成 \(\infty\)，滿流的邊容量改成 \(1\)，重新跑一遍最小割就可求出最小割邊數量；如果沒有最小割的前提，直接把所有邊的容量設成 \(1\)，求一遍最小割就好了。

問題模型 1

有 \(n\) 個物品和兩個集合 \(A,B\)，如果一個物品沒有放入 \(A\) 集合會花費 \(a_i\)，沒有放入 \(B\) 集合會花費 \(b_i\)；還有若干個形如 \(u_i,v_i,w_i\) 限制條件，表示如果 \(u_i\) 和 \(v_i\) 同時不在一個集合會花費 \(w_i\)。每個物品必須且只能屬於一個集合，求最小的代價。

這是一個經典的 二者選其一 的最小割題目。我們對於每個集合設置源點 \(s\) 和匯點 \(t\)，第 \(i\) 個點由 \(s\) 連一條容量為 \(a_i\) 的邊、向 \(t\) 連一條容量為 \(b_i\) 的邊。對於限制條件 \(u,v,w\)，我們在 \(u,v\) 之間連容量為 \(w\) 的雙向邊。

注意到當源點和匯點不相連時，代表這些點都選擇了其中一個集合。如果將連向 \(s\) 或 \(t\) 的邊割開，表示不放在 \(A\) 或 \(B\) 集合，如果把物品之間的邊割開，表示這兩個物品不放在同一個集合。

最小割就是最小花費。

問題模型 2

最大權值閉合圖，即給定一張有向圖，每個點都有一個權值（可以為正或負或 \(0\)），你需要選擇一個權值和最大的子圖，使得子圖中每個點的後繼都在子圖中。

做法：建立超級源點 \(s\) 和超級匯點 \(t\)，若節點 \(u\) 權值為正，則 \(s\) 向 \(u\) 連一條有向邊，邊權即為該點點權；若節點 \(u\) 權值為負，則由 \(u\) 向 \(t\) 連一條有向邊，邊權即為該點點權的相反數。原圖上所有邊權改為 \(\infty\)。跑網絡最大流，將所有正權值之和減去最大流，即為答案。

幾個小結論來證明：

  1. 每一個符合條件的子圖都對應流量網絡中的一個割。因為每一個割將網絡分為兩部分，與 \(s\) 相連的那部分滿足沒有邊指向另一部分，於是滿足上述條件。這個命題是充要的。
  2. 最小割所去除的邊必須與 \(s\) 和 \(t\) 其中一者相連。因為否則邊權是 \(\infty\)，不可能成為最小割。
  3. 我們所選擇的那部分子圖，權值和 \(=\) 所有正權值之和 \(-\) 我們未選擇的正權值點的權值之和 \(+\) 我們選擇的負權值點的權值之和。當我們不選擇一個正權值點時，其與 \(s\) 的連邊會被斷開；當我們選擇一個負權值點時，其與 \(t\) 的連邊會被斷開。斷開的邊的邊權之和即為割的容量。於是上述式子轉化為：權值和 \(=\) 所有正權值之和 \(-\) 割的容量。
  4. 於是得出結論，最大權值和 \(=\) 所有正權值之和 \(-\) 最小割 \(=\) 所有正權值之和 \(-\) 最大流。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用