Test/FordFulkerson.test.cpp

Back to top page

• category: Test
• View this file on GitHub
  • Last commit date: 2020-04-18 13:40:15+09:00
• see: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A

Depends on

• Flow/FordFulkerson.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A"
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 998244353LL;
constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
template <class T>
void chmin(T &a, T b) { a = min(a, b); }
template <class T>
void chmax(T &a, T b) { a = max(a, b); }
void debug() { cerr << "ok" << endl; }
template <class T>
void printv(const vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
}
#define call_from_test
#include "../Flow/FordFulkerson.cpp"
#undef call_from_test
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    FordFulkerson<int> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        g.addedge(u, v, c);
    }
    cout << g.maxflow(0, n - 1) << '\n';
}

#line 1 "Test/FordFulkerson.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/6/GRL_6_A"
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template <class T>
using V = vector<T>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll MOD = 998244353LL;
constexpr int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
template <class T>
void chmin(T &a, T b) { a = min(a, b); }
template <class T>
void chmax(T &a, T b) { a = max(a, b); }
void debug() { cerr << "ok" << endl; }
template <class T>
void printv(const vector<T> &v) {
    for (int i = 0; i < v.size(); i++) cout << v[i] << (i + 1 == v.size() ? '\n' : ' ');
}
#define call_from_test
#line 1 "Flow/FordFulkerson.cpp"
template <class T>
struct FordFulkerson {
    struct edge {
        int to;
        int rev;
        T cap;
    };
    vector<vector<edge>> G;
    vector<int> vis;
    FordFulkerson(int n) : G(n), vis(n) {}
    inline void addedge(int u, int v, T c) {
        G[u].emplace_back(edge{v, (int)G[v].size(), c});
        G[v].emplace_back(edge{u, (int)G[u].size() - 1, 0});
    }
    T dfs(int i, const int &t, T flow) {
        if (i == t) return flow;
        vis[i] = 1;
        for (auto &e : G[i]) {
            if (e.cap == 0 || vis[e.to]) continue;
            T x = dfs(e.to, t, min(flow, e.cap));
            if (x > 0) {
                e.cap -= x;
                G[e.to][e.rev].cap += x;
                return x;
            }
        }
        return 0;
    }
    T maxflow(const int &s, const int &t) {
        T res = 0;
        while (1) {
            fill(all(vis), 0);
            T inc = dfs(s, t, INF);
            if (inc == 0) break;
            res += inc;
        }
        return res;
    }
};
#line 27 "Test/FordFulkerson.test.cpp"
#undef call_from_test
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    FordFulkerson<int> g(n);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        g.addedge(u, v, c);
    }
    cout << g.maxflow(0, n - 1) << '\n';
}

Back to top page