Minimum cut

Concepts

Cut

For a flow network $G=(V,E)$, a cut is a partition of vertices: partition 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

The capacity $(S,T)$ of a cut $c(S,T)$ is the sum of the capacities of all edges from $S$ to $T$, namely $c(S,T)=\sum_{u\in S,v\in T}c(u,v)$. We may also write $c(s,t)$ for $c(S,T)$.

Minimum cut

A minimum cut is a cut $(S,T)$ whose capacity $c(S,T)$ is minimum.

Proof

Max-flow min-cut theorem

See the section on the max-flow min-cut theorem on the maximum flow page.

Code

Minimum cut

By the max-flow min-cut theorem, we can directly obtain the following code:

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

Partition

Starting DFS from the source $s$ and traversing edges with residual capacity greater than $0$ each time, we can find all vertices in the set $S$.

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 must be minimized subject to a minimum cut, first find a minimum cut, change the capacities of edges that are not saturated to $\infty$ and those that are saturated to $1$, and run minimum cut again. If there is no minimum-cut constraint, simply set every edge capacity to $1$ and find a minimum cut.

Problem model 1

There are $n$ items and two sets $A,B$. Not putting an item into $A$ costs $a_i$, and not putting it into $B$ costs $b_i$. There are also constraints of the form $u_i,v_i,w_i$, meaning that if $u_i$ and $v_i$ are not in the same set, the cost is $w_i$. Every item must belong to exactly one set; find the minimum cost.

This is a classic choose-one-of-two minimum-cut problem. Use a source $s$ and sink $t$ for the two sets; for vertex $i$, add an edge of capacity $s$ from $a_i$ and an edge of capacity $t$ to $b_i$. For a constraint $u,v,w$, add a bidirectional edge of capacity $u,v$ between $w$ and $v.

When the source and sink are disconnected, the vertices on each side represent the choices of the two sets. Cutting an edge incident to $s$ or $t$ means not putting the item in $A$ or $B$; cutting an edge between items means that the two items are not put in the same set.

The minimum cut is the minimum cost.

Problem model 2

A maximum-weight closure problem gives a directed graph in which every vertex has a weight (positive, negative, or $0$). Choose a subgraph with maximum total weight such that every successor of every vertex in the subgraph is also in the subgraph.

Construct a super-source $s$ and super-sink $t$. If vertex $u$ has positive weight, add a directed edge from $s$ to $u$ whose capacity is its weight; if $u$ has negative weight, add a directed edge from $u$ to $t$ whose capacity is the opposite of its weight. Set the capacities of all original edges to $\infty$. Run maximum flow; the sum of all positive weights minus the maximum flow is the answer.

We prove several small claims:

1. Every valid subgraph corresponds to a cut in the flow network. A cut divides the network into two parts, and the part connected to $s$ has no edge directed to the other part, so it satisfies the condition above. This correspondence is an if and only if.
2. Every edge removed by a minimum cut must be incident to either $s$ or $t$. Otherwise its capacity is $\infty$, so it cannot belong to a minimum cut.
3. The weight sum of the chosen subgraph $=$ the sum of all positive weights $-$ the sum of the positive weights of unchosen vertices $+$ the sum of the negative weights of chosen vertices. When a positive-weight vertex is not chosen, its edge to $s$ is cut; when a negative-weight vertex is chosen, its edge to $t$ is cut. The sum of the capacities of the cut edges is the cut capacity. Thus the expression becomes: weight sum $=$ sum of all positive weights $-$ cut capacity.
4. Therefore, the maximum weight sum $=$ the sum of all positive weights $-$ the minimum cut $=$ the sum of all positive weights $-$ the maximum flow.

Exercises

• 「USACO 4.4」Pollutant Control
• 「USACO 5.4」Telecowmunication
• 「Luogu 1361」Little M's Crops
• 「SHOI 2007」Kind-Hearted Voting
• Space Flight Planning Problem