Rare
 0/10

Minimum Cut

Author: Benjamin Qi

?

Resources

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

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

Minimum Node Covers

Focus Problem – read through this problem before continuing!

Resources
CPHbrief 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 , source , sink , and the following edges:

  • Edges from with capacity for each . Cutting the -th such edge corresponds to choosing the -th row.
  • Edges from with capacity for each . Cutting the -th such edge corresponds to choosing the -th column.
  • If there exists a coin in add an edge from with capacity .

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 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 or for . Each cut edge corresponds to a row or column we remove coins from.

Note that edges of the form can't be cut because they have capacity .

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) { N = _N; adj.rsz(N), cur.rsz(N); }
/// void reset() { trav(e,eds) e.flo = 0; }
void ae(int u, int v, F cap, F rcap = 0) { assert(min(cap,rcap) >= 0);
adj[u].pb(sz(eds)); eds.pb({v,0,cap});
adj[v].pb(sz(eds)); eds.pb({u,0,rcap});
}

Minimum Path Covers

Focus Problem – read through this problem before continuing!

Resources
CPHbrief mentions of node-disjoint and general path covers, Dilworth's theorem
Wikipediaproof via Konig's theorem

Solution - The Wrath of Kahn

Ignore all vertices of that can never be part of . 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) {
int x,y; re(x,y);

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
CSESEasyView Solution
Old GoldEasy
Show Tags

Max Flow

External Sol
CSANormalCheck CSA
CFNormalCheck CF
CFNormalCheck CF
CFHardCheck CF
ACHardCheck AC
FHCHardCheck FHC

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!

Give Us Feedback on Minimum Cut!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.