Flujo máximo

#include <bits/stdc++.h>
using namespace std;
 
long long max_flow(vector<vector<int>> adj, vector<vector<long long>> capacity,
                   int source, int sink) {
	int n = adj.size();
	vector<int> parent(n, -1);
	// Hallar un camino de la fuente al sumidero con capacidades no negativas
	auto reachable = [&]() -> bool {
		queue<int> q;
		q.push(source);
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (int son : adj[node]) {
				long long w = capacity[node][son];
				if (w <= 0 || parent[son] != -1) continue;
				parent[son] = node;
				q.push(son);
			}
		}
		return parent[sink] != -1;
	};
 
	long long flow = 0;
	// Mientras exista un camino de la fuente al sumidero con capacidades no
	// negativas
	while (reachable()) {
		int node = sink;
		// La capacidad mínima en el camino de la fuente al sumidero
		long long curr_flow = LLONG_MAX;
		while (node != source) {
			curr_flow = min(curr_flow, capacity[parent[node]][node]);
			node = parent[node];
		}
		node = sink;
		while (node != source) {
			// Restar la capacidad de las aristas de capacidad
			capacity[parent[node]][node] -= curr_flow;
			// Sumar el flujo actual a las aristas inversas
			capacity[node][parent[node]] += curr_flow;
			node = parent[node];
		}
		flow += curr_flow;
		fill(parent.begin(), parent.end(), -1);
	}
 
	return flow;
}
 
int main() {
	int n, m;
	cin >> n >> m;
 
	vector<vector<long long>> capacity(n, vector<long long>(n));
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
		capacity[a][b] += c;
	}
 
	cout << max_flow(adj, capacity, 0, n - 1) << endl;
}

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
const int MAXN = 5000;
const ll INF = 1e15;
 
int n, m, source, sink;
ll capacity[MAXN + 1][MAXN + 1];
ll flow[MAXN + 1][MAXN + 1];
vector<ll> excess;
vector<ll> height;
vector<ll> next_son;
queue<int> excess_vertexes;
 
void relabel(int u) {
	ll d = INF;
	for (int v = 1; v <= n; v++) {
		// Si el vecino soporta flujo.
		if (capacity[u][v] > flow[u][v]) { d = min(d, height[v]); }
	}
	if (d < INF) { height[u] = d + 1; }
}
 
// Empujar flujo del nodo u al nodo v
void push(int u, int v) {
	// delta = cuánto flujo soporta la arista
	ll d = min(excess[u], capacity[u][v] - flow[u][v]);
	// Aumentar el flujo del nodo u a v
	flow[u][v] += d;
	flow[v][u] -= d;
	// Actualizar el exceso
	excess[u] -= d;
	excess[v] += d;
	// Si el exceso de v es igual a delta, es la primera vez.
	if (d && excess[v] == d) { excess_vertexes.push(v); }
}
 
void discharge(int u) {
	// Mientras haya exceso de flujo para empujar
	while (excess[u] > 0) {
		// La siguiente parte también se puede escribir con un for
		if (next_son[u] <= n) {
			int v = next_son[u];
			// Si la arista soporta más flujo y se puede empujar hacia ella
			if (capacity[u][v] > flow[u][v] && height[u] > height[v]) {
				push(u, v);
			} else {
				next_son[u]++;
			}
		} else {
			relabel(u);
			next_son[u] = 1;
		}
	}
}
 
int main() {
	cin >> n >> m;
 
	source = 1;
	sink = n;
	excess.resize(n + 1);
	height.resize(n + 1);
	next_son.resize(n + 1);
 
	height[source] = n;
	excess[source] = INF;
 
	for (int i = 1; i <= m; i++) {
		int x, y, cap;
		cin >> x >> y >> cap;
		capacity[x][y] += cap;
	}
 
	for (int i = 1; i <= n; i++) {
		if (i == source) { continue; }
		push(source, i);
	}
 
	while (!excess_vertexes.empty()) {
		int node = excess_vertexes.front();
		excess_vertexes.pop();
		if (node != source && node != sink) { discharge(node); }
	}
 
	ll max_flow = 0;
	for (int node = 1; node <= n; node++) { max_flow += flow[node][sink]; }
 
	cout << max_flow << endl;
}

#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1e9;
 
int n, m, k;
// dist[node] = la posición de node en el camino alternante
vector<int> match, dist;
vector<vector<int>> g;
 
bool bfs() {
	queue<int> q;
	// El camino alternante empieza con nodos no emparejados
	for (int node = 1; node <= n; node++) {
		if (!match[node]) {
			q.push(node);
			dist[node] = 0;
		} else {
			dist[node] = INF;
		}
	}
 
	dist[0] = INF;
 
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		if (dist[node] >= dist[0]) { continue; }
		for (int son : g[node]) {
			// Si el match de son está emparejado
			if (dist[match[son]] == INF) {
				dist[match[son]] = dist[node] + 1;
				q.push(match[son]);
			}
		}
	}
	// Devuelve true si se encontró un camino alternante
	return dist[0] != INF;
}
 
// Devuelve true si se encontró un camino aumentante que empieza en el
// vértice node
bool dfs(int node) {
	if (node == 0) { return true; }
	for (int son : g[node]) {
		if (dist[match[son]] == dist[node] + 1 && dfs(match[son])) {
			match[node] = son;
			match[son] = node;
			return true;
		}
	}
	dist[node] = INF;
	return false;
}
 
int hopcroft_karp() {
	int cnt = 0;
	// Mientras haya un camino alternante
	while (bfs()) {
		for (int node = 1; node <= n; node++) {
			// Si node no está emparejado pero podemos emparejarlo con un
			// camino aumentante
			if (!match[node] && dfs(node)) { cnt++; }
		}
	}
	return cnt;
}
 
int main() {
	cin >> n >> m >> k;
 
	dist.resize(n + m + 1);
	match.resize(n + m + 1);
	g.resize(n + m + 1);
 
	for (int i = 1; i <= k; i++) {
		int x, y;
		cin >> x >> y;
 
		y += n;
 
		g[x].push_back(y);
		g[y].push_back(x);
	}
 
	cout << hopcroft_karp() << '\n';
	for (int node = 1; node <= n; node++) {
		if (match[node]) { cout << node << ' ' << match[node] - n << '\n'; }
	}
}