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);

	auto reachable = [&]() -> bool {
		queue<int> q;
		q.push(source);
		while (!q.empty()) {
			int node = q.front();
			q.pop();
			for (auto y : adj[node]) {
				if (capacity[node][y] <= 0 || parent[y] != -1)
                    continue;
				parent[y] = node;
				q.push(y);
			}
		}
		return parent[sink] != -1;
	};

	long long flow = 0;

	while (reachable()) {

		int node = sink;
		long long current_flow = LONG_LONG_MAX;
		
        while (node != source) {
			current_flow = min(current_flow, capacity[parent[node]][node]);
			node = parent[node];
		}

		node = sink;

		while (node != source) {
			capacity[parent[node]][node] -= current_flow;
			capacity[node][parent[node]] += current_flow;
			node = parent[node];
		}

		flow += current_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;
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED