Download Speed

#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;
 
 
bool bfs(vector<vector<long long>>& rGraph, int s, int t, vector<long long>& parent)
{
    int V = rGraph.size();
 
    vector<bool> visited(V,false);
 
    queue<int> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
 
        for (int v = 0; v < V; v++) {
            if (visited[v] == false && rGraph[u][v] > 0) {
                if (v == t) {
                    parent[v] = u;
                    return true;
                }
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
 
    return false;
}
 
long long fordFulkerson(vector<vector<long long>> graph, int s, int t)
{
    int u, v;
 
    int V = graph.size();
 
    vector<vector<long long>> rGraph(V,vector<long long>(V));
 
    for (u = 0; u < V; u++)
        for (v = 0; v < V; v++)
            rGraph[u][v] = graph[u][v];
 
 
    vector<long long> parent(V);
 
    long long max_flow = 0; 
 
    while (bfs(rGraph, s, t, parent)) {
        long long path_flow = LONG_LONG_MAX;
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            path_flow = min(path_flow, rGraph[u][v]);
        }
 
        for (v = t; v != s; v = parent[v]) {
            u = parent[v];
            rGraph[u][v] -= path_flow;
            rGraph[v][u] += path_flow;
        }
 
        max_flow += path_flow;
    }
 
    return max_flow;
}
 
int main()
{
    int n,m;
    cin >> n >> m;
 
    vector<vector<long long>> graph(n,vector<long long>(n));
 
    for(int i=0; i<m; i++){
        int a,b;
        long long c;
        cin >> a >> b >> c;
        graph[a-1][b-1]+=c;
    }
 
    cout << fordFulkerson(graph, 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