Skip to content

Minimum Cut

Concept

Cut

For a flow network graph \(G=(V,E)\), a cut is defined as a partition of vertices: dividing all vertices into two sets \(S\) and \(T=V-S\), where the source \(s\in S\) and the sink \(t\in T\).

Capacity of a Cut

We define the capacity \(c(S,T)\) of a cut \((S,T)\) as the sum of capacities of all edges from \(S\) to \(T\), i.e., \(c(S,T)=\sum_{u\in S,v\in T}c(u,v)\). Of course, we can also denote \(c(S,T)\) as \(c(s,t)\).

Minimum Cut

The minimum cut is to find a cut \((S,T)\) such that its capacity \(c(S,T)\) is minimized.

Proof

Max-Flow Min-Cut Theorem

Refer to the Max-Flow Min-Cut Theorem section on the Max-Flow page.

Code

Minimum Cut

Via the Max-Flow Min-Cut Theorem, we can directly obtain the following code:

Reference Code 
 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;
}

Solution

We can start DFS from the source \(s\), each time traversing edges with residual capacity greater than \(0\), to find all vertices in the \(S\) set.

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

Number of Cut Edges

If the number of cut edges needs to be minimized under the premise of a minimum cut, first compute the minimum cut, then change the capacity of non-saturated edges to \(\infty\), saturated edges to \(1\), and run the minimum cut algorithm again to obtain the minimum number of cut edges. If there is no minimum cut premise, simply set all edge capacities to \(1\) and compute the minimum cut.

Problem Model 1

There are \(n\) items and two sets \(A,B\). If an item is not placed into set \(A\), it incurs a cost \(a_i\); if not placed into set \(B\), it incurs a cost \(b_i\). There are also several constraints of the form \(u_i,v_i,w_i\), meaning if \(u_i\) and \(v_i\) are not in the same set, it incurs a cost \(w_i\). Each item must belong to exactly one set. Find the minimum total cost.

This is a classic either-or minimum cut problem. For each set, we set a source \(s\) and a sink \(t\). For the \(i\)-th item, connect \(s\) to it with an edge of capacity \(a_i\), and connect it to \(t\) with an edge of capacity \(b_i\). For a constraint \(u,v,w\), connect \(u\) and \(v\) with a bidirectional edge of capacity \(w\).

Note that when the source and sink are disconnected, it means all items have chosen one of the sets. Cutting an edge connected to \(s\) or \(t\) means not placing the item in \(A\) or \(B\). Cutting an edge between items means these two items are not placed in the same set.

The minimum cut is the minimum cost.

Problem Model 2

Maximum weight closure of a graph: Given a directed graph, each vertex has a weight (positive, negative, or \(0\)). Select a subgraph with maximum total weight such that for every vertex in the subgraph, all its successors are also in the subgraph.

Method: Construct a super source \(s\) and a super sink \(t\). If a vertex \(u\) has positive weight, connect \(s\) to \(u\) with a directed edge whose capacity equals the vertex weight. If \(u\) has negative weight, connect \(u\) to \(t\) with a directed edge whose capacity equals the absolute value of the vertex weight. Change all original edge capacities to \(\infty\). Compute the maximum flow. The answer is the sum of all positive weights minus the maximum flow.

A few small conclusions for proof:

  1. Every feasible subgraph corresponds to a cut in the flow network. Because a cut divides the network into two parts, the part connected to \(s\) satisfies that no edge points to the other part, thus meeting the condition. This proposition is necessary and sufficient.
  2. Edges removed by the minimum cut must be connected to either \(s\) or \(t\). Because otherwise, the edge capacity is \(\infty\), making it impossible to be part of a minimum cut.
  3. The weight sum of our chosen subgraph \(=\) sum of all positive weights \(-\) sum of positive weights of vertices we did not choose \(+\) sum of negative weights of vertices we chose. When we do not choose a positive-weight vertex, its edge to \(s\) is cut; when we choose a negative-weight vertex, its edge to \(t\) is cut. The sum of capacities of cut edges equals the cut capacity. Thus, the above formula becomes: weight sum \(=\) sum of all positive weights \(-\) cut capacity.
  4. Therefore, we conclude: maximum weight sum \(=\) sum of all positive weights \(-\) minimum cut \(=\) sum of all positive weights \(-\) maximum flow.

Exercises

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