Graph/Aizu/aizu_grl_6_a_maximum_flow2.test.cpp

View this file on GitHub
Last update: 2026-10-16 23:54:24+07:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A"

#include "../../template.h"

#include "../Flow/MaxFlowEdmondsKarp.h"


void solve() {
    int n, m; cin >> n >> m;
    EdmondsKarp mxFlow(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        mxFlow.addEdge(u, v, w);
    }
    cout << mxFlow.maxFlow(0, n-1) << '\n';
}

#line 1 "Graph/Aizu/aizu_grl_6_a_maximum_flow2.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A"

#line 2 "template.h"

#include <bits/stdc++.h>

using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll r) { return uniform_int_distribution<ll>(0, r - 1)(rng); }

const int mod = 998244353;

void solve();

int main() {
    // if (FILE* f = fopen(TASK ".inp", "r")) {

    //     fclose(f);

    //     freopen(TASK ".inp", "r", stdin);

    //     freopen(TASK ".out", "w", stdout);

    // }

    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);

    // int t; cin >> t;

    // while(t--)

        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 1 "Graph/Flow/MaxFlowEdmondsKarp.h"
// // vnoi version

// struct EdmondsKarp {

//     int n;

//     vector<vector<int>> adj;

//     vector<vector<ll>> c, f;

//     vector<int> trace;


//     EdmondsKarp(int n) : n(n), adj(n + 1), c(n + 1, vector<ll>(n + 1, 0)), f(n + 1, vector<ll>(n + 1, 0)) {}


//     void addEdge(int u, int v, ll w) {

//         adj[u].push_back(v);

//         adj[v].push_back(u);

//         c[u][v] += w;

//     }


//     bool bfs(int s, int t) {

//         trace.assign(n + 1, 0);

//         queue<int> q;

//         q.push(s);

//         trace[s] = -1;

//         while (!q.empty()) {

//             int u = q.front(); q.pop();

//             for (int v : adj[u]) {

//                 if (trace[v] || c[u][v] - f[u][v] == 0) continue;

//                 trace[v] = u;

//                 q.push(v);

//             }

//         }

//         return trace[t] != 0;

//     }


//     ll maxFlow(int s, int t) {

//         ll res = 0;

//         while (bfs(s, t)) {

//             ll delta = LLONG_MAX;

//             for (int v = t; v != s; v = trace[v]) {

//                 int u = trace[v];

//                 delta = min(delta, c[u][v] - f[u][v]);

//             }

//             for (int v = t; v != s; v = trace[v]) {

//                 int u = trace[v];

//                 f[u][v] += delta;

//                 f[v][u] -= delta;

//             }

//             res += delta;

//         }

//         return res;

//     }


//     bool inA(int u) { return trace[u] != 0; }

// };


// optimize memory version

struct EdmondsKarp {
    struct Edge {
        int v, rev;
        ll cap, flow;
    };
    int n;
    vector<vector<Edge>> g;
    vector<int> trace, id;

    EdmondsKarp(int n) : n(n), g(n + 1) {}

    void addEdge(int u, int v, ll c) {
        int iu = g[u].size(), iv = g[v].size() + (u == v);
        g[u].push_back({v, iv, c, 0});
        g[v].push_back({u, iu, 0, 0});
    }

    bool bfs(int s, int t) {
        trace.assign(n + 1, -1);
        id.assign(n + 1, -1);
        trace[s] = s;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 0; i < (int)g[u].size(); i++) {
                Edge &e = g[u][i];
                if (trace[e.v] != -1 || e.cap - e.flow == 0) continue;
                trace[e.v] = u;
                id[e.v] = i;
                q.push(e.v);
                if (e.v == t) return true;
            }
        }
        return trace[t] != -1;
    }

    ll maxFlow(int s, int t) {
        ll res = 0;
        while (bfs(s, t)) {
            ll delta = LLONG_MAX;
            for (int v = t; v != s; v = trace[v]) {
                Edge &e = g[trace[v]][id[v]];
                delta = min(delta, e.cap - e.flow);
            }
            for (int v = t; v != s; v = trace[v]) {
                Edge &e = g[trace[v]][id[v]];
                e.flow += delta;
                g[v][e.rev].flow -= delta;
            }
            res += delta;
        }
        return res;
    }

    bool inA(int u) { return trace[u] != -1; }
};
#line 5 "Graph/Aizu/aizu_grl_6_a_maximum_flow2.test.cpp"

void solve() {
    int n, m; cin >> n >> m;
    EdmondsKarp mxFlow(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        mxFlow.addEdge(u, v, w);
    }
    cout << mxFlow.maxFlow(0, n-1) << '\n';
}