Rare
0/10

# Minimum Cut

Author: Benjamin Qi

?

## 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 $0\ldots 2N+1$, source $0$, sink $2N+1$, and the following edges:

• Edges from $0\to i$ with capacity $1$ for each $1\le i\le N$. Cutting the $i$-th such edge corresponds to choosing the $i$-th row.
• Edges from $N+i\to 2N+1$ with capacity $1$ for each $1\le i\le N$. Cutting the $i$-th such edge corresponds to choosing the $i$-th column.
• If there exists a coin in $(r,c)$ add an edge from $r\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)$ 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)$ or $(i+N,2N+1)$ for $1\le i\le N$. Each cut edge corresponds to a row or column we remove coins from.

Note that edges of the form $r\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 $G$ that can never be part of $S$. 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;vi out;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

### 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!