icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/graph/Maximum_Flow.test.cpp

Depends on

Code

#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"

#include "../../graph/fordfulkerson.hpp"
#include "../../graph/mf_graph.hpp"
#include "../../template/template.hpp"

using namespace lib;

int main() {
    int n, m;
    std::cin >> n >> m;
    FordFulkerson<int> g1(n);
    mf_graph<int> g2(n);
    rep(i, 0, m) {
        int u, v, c;
        std::cin >> u >> v >> c;
        g1.add_edge(u, v, c);
        g2.add_edge(u, v, c);
    }
    int flow = g1.flow(0, n - 1);
    assert(flow == g2.flow(0, n - 1));
    std::cout << flow << '\n';
}
#line 1 "test/graph/Maximum_Flow.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"

#line 2 "template/template.hpp"

#include <bits/stdc++.h>

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <typename T> bool chmin(T &a, const T &b) {
    if (a <= b) return false;
    a = b;
    return true;
}
template <typename T> bool chmax(T &a, const T &b) {
    if (a >= b) return false;
    a = b;
    return true;
}

namespace lib {

using namespace std;

}  // namespace lib

// using namespace lib;
#line 3 "graph/fordfulkerson.hpp"

namespace lib {
using namespace std;

template <typename fa> struct FordFulkerson {
    struct edge {
        int to;
        fa cap;
        int rev;
        bool isrev;
    };

    const fa INF;
    vector<vector<edge>> g;
    vector<int> used;
    int ts;

    explicit FordFulkerson(int v)
        : INF(numeric_limits<fa>::max()), g(v), used(v, -1), ts(0) {}

    void add_edge(int from, int to, fa cap) {
        g[from].push_back((edge){to, cap, (int)g[to].size(), false});
        g[to].push_back((edge){from, 0, (int)g[from].size() - 1, true});
    }
    fa dfs(int v, int t, fa flow) {
        if (v == t) return flow;
        used[v] = ts;
        for (auto &e : g[v]) {
            if (e.cap > 0 && used[e.to] != ts) {
                fa d = dfs(e.to, t, min(flow, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    g[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    fa flow(int s, int t) {
        fa ret = 0;
        for (fa f; (f = dfs(s, t, INF)) > 0; ts++) ret += f;
        ts++;
        return ret;
    }
};

}  // namespace lib
#line 3 "graph/mf_graph.hpp"

namespace lib {
using namespace std;

template <class Cap> struct mf_graph {
    struct edge {
        int from, to;
        Cap cap, flow;
    };

    struct nedge {
        int to, rev;
        Cap cap;
    };

    int nn;
    vector<pair<int, int>> pos;
    vector<vector<nedge>> g;

    mf_graph() : nn(0) {}
    explicit mf_graph(int n) : nn(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        int m = pos.size();
        pos.push_back({from, int(g[from].size())});
        int frid = int(g[from].size());
        int toid = int(g[to].size());
        if (from == to) toid++;
        g[from].push_back(nedge{to, toid, cap});
        g[to].push_back(nedge{from, frid, 0});
        return m;
    }

    Cap flow(int s, int t) {
        return flow(s, t, numeric_limits<Cap>::max());
    }

    Cap flow(int s, int t, Cap flow_limit) {
        vector<int> lv(nn), iter(nn);
        queue<int> q;

        auto bfs = [&]() {
            fill(all(lv), -1);
            lv[s] = 0;
            queue<int>().swap(q);
            q.push(s);
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || lv[e.to] >= 0) continue;
                    lv[e.to] = lv[v] + 1;
                    if (e.to == t) return;
                    q.push(e.to);
                }
            }
        };

        auto dfs = [&](auto self, int v, Cap up) {
            if (v == s) return up;
            Cap res = 0;
            int lvvv = lv[v];
            for (int& i = iter[v]; i < int(g[v].size()); i++) {
                nedge& e = g[v][i];
                if (lvvv <= lv[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d = self(self, e.to, min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) return res;
            }
            lv[v] = nn;
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (lv[t] == -1) break;
            fill(all(iter), 0);
            Cap f = dfs(dfs, t, flow_limit - flow);
            if (!f) break;
            flow += f;
        }
        return flow;
    }

    /*

if you want other functions, take from here
NOT VERIFIED.

edge get_edge(int i) {
    int m = int(pos.size());
    auto _e = g[pos[i].first][pos[i].second];
    auto _re = g[_e.to][_e.rev];
    return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}

vector<edge> edges() {
    int m = int(pos.size());
    vector<edge> result;
    for (int i = 0; i < m; i++) {
        result.push_back(get_edge(i));
    }
    return result;
}

void change_edge(int i, Cap new_cap, Cap new_flow) {
    int m = int(pos.size());
    auto& _e = g[pos[i].first][pos[i].second];
    auto& _re = g[_e.to][_e.rev];
    _e.cap = new_cap - new_flow;
    _re.cap = new_flow;
}

std::vector<bool> min_cut(int s) {
    vector<bool> visited(_n);
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        visited[p] = true;
        for (auto e : g[p]) {
            if (e.cap && !visited[e.to]) {
                visited[e.to] = true;
                q.push(e.to);
            }
        }
    }
    return visited;
}

    */
};

}  // namespace lib
#line 7 "test/graph/Maximum_Flow.test.cpp"

using namespace lib;

int main() {
    int n, m;
    std::cin >> n >> m;
    FordFulkerson<int> g1(n);
    mf_graph<int> g2(n);
    rep(i, 0, m) {
        int u, v, c;
        std::cin >> u >> v >> c;
        g1.add_edge(u, v, c);
        g2.add_edge(u, v, c);
    }
    int flow = g1.flow(0, n - 1);
    assert(flow == g2.flow(0, n - 1));
    std::cout << flow << '\n';
}
Back to top page