Download Speed

input/code.cpp: In function 'bool there_is_bfs(std::vector<std::vector<long long int> >&, long long int, long long int, std::vector<long long int>&)':
input/code.cpp:25:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (long long i = 0; i < adj.size(); ++i)
      |                               ~~^~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;


bool there_is_bfs(vector<vector<long long>> &adj, long long s, long long t, vector<long long> &parent)
{
    // No node has been visited yet
    vector<bool> visited(adj.size(), false);

    // Queue for BFS
    queue<long long> q;
    q.push(s);
    visited[s] = true;
    parent[s] = -1;

    // BFS
    while (!q.empty()) {
        long long u = q.front();
        q.pop();

        for (long long i = 0; i < adj.size(); ++i)
        {
            if (!visited[i] and adj[u][i] > 0) {
                if (i == t) {
                    parent[i] = u;
                    return true;
                }
                q.push(i);
                parent[i] = u;
                visited[i] = true;
            }
        }
    }

    // There is no path
    return false;
}


long long ford_fulkerson(vector<vector<long long>> &graph, long long start, long long end)
{
    vector<long long> parent(graph.size());
    long long max_flow = 0;

    // While there is a path with positive capacities from start to end
    while (there_is_bfs(graph, start, end, parent)) {

        // Calculate path flow for the found path with bfs
        long long path_flow = LLONG_MAX;
        for (long long i = end; i != start; i = parent[i]) {
            long long v = parent[i];
            path_flow = min(path_flow, graph[v][i]);
        }

        // Update max flow
        max_flow += path_flow;

        // Update residual capacities
        for (long long i = end; i != start; i = parent[i]) {
            long long v = parent[i];
            graph[v][i] -= path_flow;
            graph[i][v] += path_flow;
        }
    }

    return max_flow;
}


int main() {
    long long n, m;
    cin >> n >> m;

    // Build graph with capacities
    vector<vector<long long>> capacity(n+1, vector<long long>(n+1, 0));

    for (long long i = 0; i < m; ++i) {
        long long a, b, c;
        cin >> a >> b >> c;
        capacity[a][b] += c;
    }

    // Calculate max flow
    cout << ford_fulkerson(capacity, 1, n) << 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