Corte mínimo

Recursos

Los recursos de abajo incluyen muchas aplicaciones ingeniosas del corte mínimo, incluido el problema de cierre  (closure problem).

Teorema del corte mínimo y flujo máximo

Dada una red de flujo con fuente $s$ y sumidero $t$, un corte $s$-$t$ es una partición de los vértices en dos conjuntos $S$ y $T$ con $s \in S$ y $t \in T$. Su capacidad es la capacidad total de las aristas que cruzan del lado de la fuente al lado del sumidero:

(Las aristas que apuntan al otro lado, de $T$ a $S$, no contribuyen.) Cortar todas estas aristas desconecta $s$ de $t$, así que intuitivamente la capacidad de un corte es una cota superior de cuánto flujo puede ir de $s$ a $t$. En efecto, para cualquier flujo $f$ y cualquier corte $(S, T)$,

donde $\operatorname{val}(f)$ es el flujo total de $s$ a $t$. Así, todo flujo está acotado por todo corte.

Aquí hay una ilustración de un corte $s$-$t$: los nodos rojos están en $S$ y los azules en $T$. Es importante que $S$ y $T$ no necesitan ser conexos: el único requisito es que $s \in S$ y $t \in T$. La capacidad de este corte es la suma de las capacidades subrayadas en verde, $2 + 1 = 3$. El flujo a través de este corte se obtiene de los números subrayados en amarillo, $2 - 1 + 1 = 2$, que coincide con el flujo $s$-$t$ real, $\operatorname{val}(f)$. Nótese también que en esta instancia el flujo a través del corte ($2$) es menor que su capacidad ($3$). Sin embargo, si elegimos $S = \{s\}$ y $T = V \setminus \{s\}$, el flujo a través del corte ($2$) y su capacidad ($2$) serán iguales.

El teorema del corte mínimo y flujo máximo afirma que, en general, siempre podemos alcanzar esa igualdad:

El valor máximo de un flujo $s$-$t$ es igual a la capacidad mínima de un corte $s$-$t$.

Para mostrar que la cota es justa, solo hace falta construir un flujo $f$ y un corte $(S, T)$ tales que $\operatorname{val}(f) = \operatorname{cap}(S, T)$. Para ello, tomamos $f$ como cualquier flujo máximo y usamos el hecho de que $f$ no puede tener caminos aumentantes restantes para construir un corte $(S, T)$ de capacidad mínima. De hecho, este corte se puede construir tomando $S$ como el conjunto de nodos alcanzables desde la fuente $s$ en el grafo residual (y $T$ como el conjunto de todos los demás nodos, es decir, $V - S$). Para ver por qué, consideremos el siguiente diagrama:

Por definición, las aristas rojas deben estar saturadas hasta su capacidad; de lo contrario, los nodos de $S$ podrían alcanzar nodos de $T$. De forma similar, las aristas azules deben tener flujo 0. Por lo tanto, el flujo a través de este corte es igual a la capacidad de este corte, como se deseaba.

Cubiertas mínimas de nodos

Solución - Coin Grid

Este problema pide hallar una cubierta mínima de nodos de un grafo bipartito. Construimos un grafo de flujo con vértices etiquetados $0\ldots 2N+1$, fuente $0$, sumidero $2N+1$, y las siguientes aristas:

• Aristas de $0\to i$ con capacidad $1$ para cada $1\le i\le N$. Cortar la $i$-ésima de esas aristas corresponde a elegir la $i$-ésima fila.
• Aristas de $N+i\to 2N+1$ con capacidad $1$ para cada $1\le i\le N$. Cortar la $i$-ésima de esas aristas corresponde a elegir la $i$-ésima columna.
• Si existe una moneda en $(r,c)$, agregamos una arista de $r\to N+c$ con capacidad $\infty$.

Primero hallamos un flujo máximo, que nos dice cuántas aristas de capacidad 1 hay que cortar. Para hallar el corte mínimo en sí, hacemos BFS otra vez desde la fuente. Las aristas $(a,b)$ que conectan vértices alcanzables desde la fuente (lev[a] != -1) con vértices que no lo son (lev[b] == -1) forman parte del corte mínimo. En este caso, cada una de esas aristas debe ser de la forma $(0,i)$ o $(i+N,2N+1)$ para $1\le i\le N$. Cada arista cortada corresponde a una fila o columna de la que quitamos monedas.

Nótese que las aristas de la forma $r\to N+c$ no se pueden cortar porque tienen capacidad $\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) {
		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});
	}
	vi lev;
	V<vi::iterator> cur;
	bool bfs(int s, int t) {  // level = shortest distance from source
		lev = vi(N, -1);
		F0R(i, N) cur[i] = begin(adj[i]);
		queue<int> q({s});
		lev[s] = 0;
		while (sz(q)) {
			int u = q.ft;
			q.pop();
			trav(e, adj[u]) {
				const Edge &E = eds[e];
				int v = E.to;
				if (lev[v] < 0 && E.flo < E.cap) q.push(v), lev[v] = lev[u] + 1;
			}
		}
		return lev[t] >= 0;
	}
	F dfs(int v, int t, F flo) {
		if (v == t) return flo;
		for (; cur[v] != end(adj[v]); cur[v]++) {
			Edge &E = eds[*cur[v]];
			if (lev[E.to] != lev[v] + 1 || E.flo == E.cap) continue;
			F df = dfs(E.to, t, min(flo, E.cap - E.flo));
			if (df) {
				E.flo += df;
				eds[*cur[v] ^ 1].flo -= df;
				return df;
			}  // saturated >=1 one edge
		}
		return 0;
	}
	F maxFlow(int s, int t) {
		F tot = 0;
		while (bfs(s, t))
			while (F df = dfs(s, t, numeric_limits<F>::max())) tot += df;
		return tot;
	}
};
 
int main() {
	int n;
	re(n);
	Dinic D;
	D.init(2 * n + 2);
	F0R(i, n) {
		D.ae(0, i + 1, 1);
		D.ae(i + 1 + n, 2 * n + 1, 1);
		F0R(j, n) {
			char c;
			re(c);
			if (c == 'o') D.ae(i + 1, j + 1 + n, MOD);  // some big capacity -> not cut
		}
	}
	ps(D.maxFlow(0, 2 * n + 1));
	D.bfs(0, 2 * n + 1);
	FOR(i, 1, n + 1) if (D.lev[i] < 0) ps(1, i);  // edge from 0 to i is cut
	FOR(i, 1, n + 1)
	if (D.lev[i + n] >= 0) ps(2, i);  // edge from i+n to 2*n+1 is cut
}

Cubiertas mínimas de caminos

Solución - The Wrath of Kahn

Ignoramos todos los vértices de $G$ que nunca pueden formar parte de $S$. Luego nuestro objetivo es hallar el tamaño de una anticadena máxima en el grafo restante, que como se menciona en CPH es simplemente una instancia de cubierta mínima de caminos.

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);
		T.ae(x, y);
		link[x][y] = 1;
	}
	F0R(k, n) F0R(a, n) F0R(b, n) link[a][b] |= link[a][k] & link[k][b];
	T.sort(n);
	vi bad;
	F0R(i, n) if (T.in[i]) bad.pb(i);  // cannot be part of S
	trav(a, bad) F0R(i, n) link[a][i] = link[i][a] = 0;
	F0R(i, n) {
		D.ae(2 * n, i, 1);
		D.ae(i + n, 2 * n + 1, 1);
	}
	F0R(i, n) F0R(j, n) if (link[i][j]) D.ae(i, n + j, 1);
	int chain = n - sz(bad) - D.maxFlow(2 * n + 2, 2 * n, 2 * n + 1);
	ps(chain);
}

Problemas