Rare
 0/10

Minimum Cut

Author: Benjamin Qi

?

Edit This Page

Resources

The resources below include many clever applications of min cut, including the Closure Problem.

Resources
CPC

Slides from "Algorithm Design." Min-Cut Max-Flow Theorem, applications of flow / min cut.

Minimum Node Covers

Focus Problem – try your best to solve this problem before continuing!

Resources
CPH

brief mentions of Hall's Theorem, Konig's Theorem

Solution - Coin Grid

This problem asks us to find a minimum node cover of a bipartite graph. Construct a flow graph with vertices labeled 02N+10\ldots 2N+1, source 00, sink 2N+12N+1, and the following edges:

  • Edges from 0i0\to i with capacity 11 for each 1iN1\le i\le N. Cutting the ii-th such edge corresponds to choosing the ii-th row.
  • Edges from N+i2N+1N+i\to 2N+1 with capacity 11 for each 1iN1\le i\le N. Cutting the ii-th such edge corresponds to choosing the ii-th column.
  • If there exists a coin in (r,c)(r,c) add an edge from rN+cr\to N+c with capacity \infty.

First we find a max flow, which tells us the number of edges with capacity 1 we need to cut. To find the min cut itself, BFS from the source once more time. Edges (a,b)(a,b) connecting vertices that are reachable from the source (lev[a] != -1) to vertices that aren't (lev[b] == -1) are part of the minimum cut. In this case, each of these edges must be of the form (0,i)(0,i) or (i+N,2N+1)(i+N,2N+1) for 1iN1\le i\le N. Each cut edge corresponds to a row or column we remove coins from.

Note that edges of the form rN+cr\to N+c can't be cut because they have capacity \infty.

struct Dinic { // flow template
using F = ll; // flow type
struct Edge {
int to;
F flo, cap;
};
int N;
V<Edge> eds;
V<vi> adj;
void init(int _N) {

Minimum Path Covers

Focus Problem – try your best to solve this problem before continuing!

Resources
CPH

brief mentions of node-disjoint and general path covers, Dilworth's theorem

Wikipedia

proof via Konig's theorem

Solution - The Wrath of Kahn

Ignore all vertices of GG that can never be part of SS. Then our goal is to find the size of a maximum antichain in the remaining graph, which as mentioned in CPH is just an instance of maximum path cover.

TopoSort<500> T;
int n, m;
bool link[500][500];
vi out[500];
Dinic<1005> D;
int main() {
setIO();
re(n, m);
F0R(i, m) {

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Old GoldEasy
Show TagsMax Flow
CSANormal
CFNormal
CFNormal
CFHard
ACHard
FHCHard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!