Skip to Content
CTRL K

Bipartite Matching

Explicación

Este problema pide computar el matching máximo en un grafo bipartito con LL vértices a la izquierda, RR vértices a la derecha y MM aristas que los conectan.

Lo resolvemos reduciéndolo a un problema de flujo máximo.

Construcción de la red de flujo

Construimos una red de flujo de la siguiente forma:

  1. Creamos un nodo fuente S y un nodo sumidero T.
  2. Para cada vértice del lado izquierdo, añadimos una arista de S a ese vértice con capacidad 1.
  3. Para cada vértice del lado derecho, añadimos una arista de ese vértice a T con capacidad 1.
  4. Para cada arista bipartita (ai,bi)(a_i, b_i), añadimos una arista dirigida del vértice izquierdo aia_i al vértice derecho bib_i con capacidad 1.

Como cada arista tiene capacidad 1, cada unidad de flujo corresponde a seleccionar esa arista en el matching. Las restricciones de capacidad garantizan que cada vértice se puede emparejar con a lo sumo otro vértice.

Así, el flujo máximo de S a T es exactamente el matching bipartito máximo.

Implementamos esto con el algoritmo de Dinic, que normalmente corre en O(V2E)\mathcal{O}(V^2 E). Después de ejecutar el algoritmo de flujo, podemos recuperar el matching comprobando qué aristas entre las particiones izquierda y derecha tienen flow = 1.

También se puede consultar este  video para entender bien el algoritmo de Dinic.

Redes unitarias

Un grafo en el que para cualquier vértice excepto SS y TT hay o bien una única arista entrante o bien una única arista saliente con capacidad unitaria se llama red unitaria. Podemos notar que el grafo que hemos construido es una red unitaria.

Se puede demostrar que el algoritmo de Dinic corre en tiempo O(EV)\mathcal{O}(E\sqrt{V}) sobre redes unitarias (fuente ).

Implementación

Complejidad temporal: O(EV)\mathcal{O}(E\sqrt{V})

 
#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{Dinic's Algorithm}
struct Edge {
	int to, rev, cap;
};
 
struct Dinic {
	int n;
	vector<vector<Edge>> g;
	vector<int> level, it;
 
	Dinic(int n) : n(n) {
		g.assign(n, {});
		level.resize(n);
		it.resize(n);
	}
 
	void addEdge(int u, int v, int cap) {
		g[u].push_back({v, (int)g[v].size(), cap});
		g[v].push_back({u, (int)g[u].size() - 1, 0});
	}
 
	bool bfs(int s, int t) {
		fill(level.begin(), level.end(), -1);
		queue<int> q;
		level[s] = 0;
		q.push(s);
 
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (auto &e : g[v]) {
				if (e.cap > 0 && level[e.to] == -1) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
		return level[t] != -1;
	}
 
	int dfs(int v, int t, int f) {
		if (v == t) return f;
 
		for (int &i = it[v]; i < g[v].size(); i++) {
			Edge &e = g[v][i];
 
			if (e.cap > 0 && level[e.to] == level[v] + 1) {
				int pushed = dfs(e.to, t, min(f, e.cap));
 
				if (pushed) {
					e.cap -= pushed;
					g[e.to][e.rev].cap += pushed;
					return pushed;
				}
			}
		}
		return 0;
	}
 
	int maxFlow(int s, int t) {
		int flow = 0;
 
		while (bfs(s, t)) {
			fill(it.begin(), it.end(), 0);
			int f;
			while ((f = dfs(s, t, INT_MAX))) flow += f;
		}
 
		return flow;
	}
};
// EndCodeSnip
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int n, m, e;
	cin >> n >> m >> e;
 
	// BeginCodeSnip{Flow Network Construction}
	int S = 0;
	int T = n + m + 1;
 
	Dinic dinic(n + m + 2);
 
	for (int i = 0; i < e; i++) {
		int u, v;
		cin >> u >> v;
		u++;
		v++;
		dinic.addEdge(u, n + v, 1);
	}
 
	for (int i = 1; i <= n; i++) dinic.addEdge(S, i, 1);
 
	for (int i = 1; i <= m; i++) dinic.addEdge(n + i, T, 1);
	// EndCodeSnip
 
	cout << dinic.maxFlow(S, T) << "\n";
 
	for (int i = 1; i <= n; i++) {
		for (auto &e : dinic.g[i]) {
			if (e.to > n && e.to <= n + m && e.cap == 0)
				cout << i - 1 << " " << e.to - n - 1 << "\n";
		}
	}
}
Fundamentos