Download Speed

input/code.cpp: In function 'long long int dfs(int, long long int, int)':
input/code.cpp:46:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int &i = ptr[u]; i < graph[u].size(); i++) {
      |                           ~~^~~~~~~~~~~~~~~~~

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

using namespace std;

struct Edge {
    int to;
    int rev;
    long long cap;
};

vector<vector<Edge>> graph;
vector<int> level, ptr;

void add_edge(int from, int to, long long cap) {
    graph[from].push_back(Edge{to, static_cast<int>(graph[to].size()), cap});
    graph[to].push_back(Edge{from, static_cast<int>(graph[from].size()) - 1, 0});  // reverse edge
}

bool bfs(int s, int t) {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    q.push(s);
    level[s] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (const auto &e : graph[u]) {
            if (level[e.to] == -1 && e.cap > 0) {
                level[e.to] = level[u] + 1;
                q.push(e.to);
                if (e.to == t) return true;
            }
        }
    }
    
    return false;
}

long long dfs(int u, long long flow, int t) {
    if (u == t) return flow;
    for (int &i = ptr[u]; i < graph[u].size(); i++) {
        Edge &e = graph[u][i];
        
        if (e.cap > 0 && level[e.to] == level[u] + 1) {
            long long min_cap = dfs(e.to, min(flow, e.cap), t);
            if (min_cap > 0) {
                e.cap -= min_cap;
                graph[e.to][e.rev].cap += min_cap;
                return min_cap;
            }
        }
    }
    
    return 0;
}

long long dinic(int s, int t) {
    long long max_flow = 0;
    
    while (bfs(s, t)) {
        fill(ptr.begin(), ptr.end(), 0);
        while (long long flow = dfs(s, LLONG_MAX, t)) {
            max_flow += flow;
        }
    }
    
    return max_flow;
}

int main() {
    int n, m;
    cin >> n >> m;
    graph.resize(n + 1);
    level.resize(n + 1);
    ptr.resize(n + 1);
    
    int a, b;
    long long c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        add_edge(a, b, c);
    }
    
    cout << dinic(1, n) << endl;
    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