Download Speed

#include <bits/stdc++.h>

using namespace std;

//Definitions for quicker writing
#define REP(i,a,b) for (int i = a; i < b; i++)
#define PB push_back
#define MP make_pair
#define F first
#define S second

//Typedefs for quicker writing
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
typedef pair<long long, long long> pl;

//Max values
const long long lmx = LLONG_MAX;
const int imx = INT_MAX;

//Since max 500 comps
vector<ll> adj[501];
ll weights[501][501];

ll bfs(ll size, ll *path, ll last) {
	REP(i,0, size){
		path[i] = 0;
	}
	path[0] = -1;
	queue<pl> q;
	q.push({1, lmx});
	ll cur, minflow;
	while (!q.empty()) {
		cur = q.front().first - 1;
		minflow = q.front().second;
		q.pop();

		for (auto n : adj[cur]) {
			if (!weights[cur][n] || path[n]) {
				continue;
			}
			path[n] = cur + 1;
			if (n == last) {
				return min(minflow, weights[cur][n]);
			}
			q.push({n + 1, min(minflow, weights[cur][n])});
		}
	}
	return 0;
}

int main() {
	//IO optimization
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	//Input definition
	int n;
	int m;

	//Read In
	cin >> n >> m;
	
	int a, b, c;
	REP(i,0,m){
		cin >> a >> b >> c;
		a--;
		b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
		weights[a][b] += c;
	}

	//Main part
	ll res = 0;
	ll path[n];

	ll cur;
	ll val;
	while ((val = bfs(n, path, n - 1))) {
		cur = n - 1;
		res += val;
		while (path[cur] != -1) {
			weights[path[cur] - 1][cur] -= val;
			weights[cur][path[cur] - 1] += val;
			cur = path[cur] - 1;
		}
	}

	//Write out
	cout << res << "\n";
		
	//Return
	return 0;

}

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