test/MaxFlow.test.cpp

• View this file on GitHub
• Last update: 2021-09-12 23:44:25+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_A

Depends on

• Max Flow (Dinic) (graph/MaxFlow.cpp)
• template/template.cpp

Code

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

#include "../graph/MaxFlow.cpp"

int main(){
    ll V,E;cin>>V>>E;
    Dinic F(V);
    rep(i,E){
        int u,v,c;cin>>u>>v>>c;
        F.addEdge(u,v,c);
    }
    cout<<F.maxFlow(0,V-1)<<"\n";
}

#line 1 "test/MaxFlow.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_6_A"

#line 2 "template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i, n) for (int i = 1; i < n; i++)
#define rev(i, n) for (int i = n - 1; i >= 0; i--)
#define REV(i, n) for (int i = n - 1; i > 0; i--)
#define all(v) v.begin(), v.end()
#define PL pair<ll, ll>
#define PI pair<int, int>
#define pi acos(-1)
#define len(s) (int)s.size()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), v.end());
#define comid(v, x) lower_bound(all(v), x) - v.begin()

template<class T>
using prique=priority_queue<T,vector<T>,greater<>>;

template <class T, class U>
inline bool chmin(T &a, U b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T, class U>
inline bool chmax(T &a, U b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
constexpr ll inf = 3e18;
#line 3 "graph/MaxFlow.cpp"

struct Dinic {
    struct Edge {
        ll to, cap, rev;
    };
    vector<vector<Edge>> G;
    vector<ll> level, iter;
    void addEdge(ll from, ll to, ll cap) {
        G[from].push_back({to, cap, len(G[to])});
        G[to].push_back({from, 0, len(G[from]) - 1});
    }
    void bfs(ll s) {
        fill(all(level), -1);
        level[s] = 0;
        queue<ll> que;
        que.push(s);
        while (len(que)) {
            ll p = que.front();
            que.pop();
            for (Edge e : G[p]) {
                if (e.cap > 0 && level[e.to] == -1) {
                    level[e.to] = level[p] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    ll dfs(ll v, ll t, ll f) {
        if (v == t) return f;
        for (ll &i = iter[v]; i < len(G[v]); i++) {
            Edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] > level[v]) {
                ll d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    ll maxFlow(ll s, ll t) {
        ll flow = 0;
        while (1) {
            bfs(s);
            if (level[t] < 0) return flow;
            fill(all(iter), 0);
            ll f = 0;
            while ((f = dfs(s, t, inf)) > 0) {
                flow += f;
            }
        }
    }
    Dinic(ll N) : G(N), level(N), iter(N) {}
};
/*
@brief Max Flow (Dinic)
@docs docs/MaxFlow.md
*/
#line 4 "test/MaxFlow.test.cpp"

int main(){
    ll V,E;cin>>V>>E;
    Dinic F(V);
    rep(i,E){
        int u,v,c;cin>>u>>v>>c;
        F.addEdge(u,v,c);
    }
    cout<<F.maxFlow(0,V-1)<<"\n";
}

Back to top page