Download Speed

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>
 
using namespace std;
 
struct Edge {
    int to;        
    int rev;        
    long long cap; 
};
 
const int MAXN = 501;          
vector<Edge> graph[MAXN];      
int level[MAXN];              
int iter[MAXN];                
 
void add_edge(int from, int to, long long cap) {
    Edge forward = {to, (int)graph[to].size(), cap};
    Edge backward = {from, (int)graph[from].size(), 0};
    graph[from].push_back(forward);
    graph[to].push_back(backward);
}
 
void bfs(int s, int n) {
    fill(level, level + n + 1, -1);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        for (const Edge& e : graph[v]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}
 
long long dfs(int v, int t, long long upTo) {
    if (v == t) return upTo;
    for (int &i = iter[v]; i < (int)graph[v].size(); ++i) {
        Edge &e = graph[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            long long d = dfs(e.to, t, min(upTo, e.cap));
            if (d > 0) {
                e.cap -= d;
                graph[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}
 
long long max_flow(int s, int t, int n) {
    long long flow = 0;
    const long long INF = numeric_limits<long long>::max();
    while (true) {
        bfs(s, n);
        if (level[t] < 0) break;
        fill(iter, iter + n + 1, 0);
        long long f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
    return flow;
}
 
int main() {
 
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < m; ++i) {
        int a, b;
        long long c;
        cin >> a >> b >> c;
        add_edge(a, b, c);
    }
 
    int s = 1;         
    int t = n;      
 
    cout << max_flow(s, t, n) << "\n";
 
    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