Download Speed

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

#include <bits/stdc++.h>
using namespace std;

// Structure to represent an edge in the flow network
struct Edge {
    int to;         // Destination node
    int rev;        // Index of the reverse edge in the adjacency list of 'to'
    long long cap;  // Capacity of the edge
};

// Class to represent the flow network and perform Dinic's Algorithm
class MaxFlow {
public:
    int N; // Number of nodes
    vector<vector<Edge>> graph; // Adjacency list
    vector<int> level; // Level of each node for BFS
    vector<int> ptr;   // Current edge to explore for each node in DFS

    // Constructor to initialize the graph
    MaxFlow(int N) : N(N), graph(N + 1), level(N + 1, -1), ptr(N + 1, 0) {}

    // Function to add an edge to the graph
    void add_edge(int from, int to, long long cap) {
        Edge a = {to, (int)graph[to].size(), cap};
        Edge b = {from, (int)(graph[from].size()), 0};
        graph[from].push_back(a);
        graph[to].push_back(b);
    }

    // BFS to construct levels
    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 v = q.front(); q.pop();
            for(auto &e : graph[v]) {
                if(e.cap > 0 && level[e.to] == -1){
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    // DFS to find augmenting paths
    long long dfs(int v, int t, long long pushed) {
        if(v == t) return pushed;
        for(int &cid = ptr[v]; cid < graph[v].size(); cid++) {
            Edge &e = graph[v][cid];
            if(e.cap > 0 && level[e.to] == level[v] + 1){
                long long tr = dfs(e.to, t, min(pushed, e.cap));
                if(tr > 0){
                    e.cap -= tr;
                    graph[e.to][e.rev].cap += tr;
                    return tr;
                }
            }
        }
        return 0;
    }

    // Function to compute the maximum flow from s to t
    long long max_flow_func(int s, int t){
        long long flow = 0;
        while(bfs(s, t)){
            fill(ptr.begin(), ptr.end(), 0);
            while(long long pushed = dfs(s, t, 1e18)){
                flow += pushed;
            }
        }
        return flow;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    MaxFlow mf(n);
    
    // Read connections and build the graph
    for(int i = 0; i < m; i++){
        int a, b;
        long long c;
        cin >> a >> b >> c;
        mf.add_edge(a, b, c);
    }
    
    // Compute the maximum flow from node 1 to node n
    long long max_flow = mf.max_flow_func(1, n);
    cout << max_flow;
}

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