Download Speed

#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 (auto 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) {
			// Restamos la capacidad de las aristas de capacidad
			capacity[parent[node]][node] -= curr_flow;
			// Sumamos 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, 0));
	vector<vector<int>> adj(n);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		--a;
		--b;
		adj[a].push_back(b);
		adj[b].push_back(a);
		capacity[a][b] += c;
	}
 
	cout << max_flow(adj, capacity, 0, n - 1) << endl;
}