Minimum Cut
Author: Benjamin Qi
?
Prerequisites
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 – read through 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 , 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 templateusing F = ll; // flow typestruct 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 | ||||
---|---|---|---|---|
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 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
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
CSES | Easy | ||||
Old Gold | Easy | Show TagsMax Flow | |||
CSA | Normal | ||||
CF | Normal | ||||
CF | Normal | ||||
CF | Hard | ||||
AC | Hard | ||||
FHC | Hard |