test/AOJ/GRL_7_A.test.cpp

View this file on GitHub
Last update: 2024-10-01 17:09:04+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A
Link: View error logs on GitHub Actions

Depends on

Code

#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#include "graph/flow/ford-fullkerson.hpp"
#include "template/template.hpp"

int main() {
    INT(X, Y, E);
    Graph<int> G(X + Y + 2);
    for (int i = 0; i < X; i++) {
        G.addedge(0, i + 1, 1);
    }
    for (int i = 0; i < E; i++) {
        INT(x, y);
        x++;
        y += X + 1;
        G.addedge(x, y, 1);
    }
    for (int i = 0; i < Y; i++) {
        G.add_undirected_edge(i + X + 1, X + Y + 1, 1);
    }
    FordFulkerson<int> ff;
    cout << ff.solve(G, 0, X + Y + 1) << endl;
}

#line 1 "test/AOJ/GRL_7_A.test.cpp"
#define PROBLEM \
    "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A"
#line 2 "template/template.hpp"
#include <bits/stdc++.h>
#line 3 "template/macro.hpp"

#define overload3(_1, _2, _3, name, ...) name
#define all1(v) std::begin(v), std::end(v)
#define all2(v, a) std::begin(v), std::begin(v) + a
#define all3(v, a, b) std::begin(v) + a, std::begin(v) + b
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define rall1(v) std::rbegin(v), std::rend(v)
#define rall2(v, a) std::rbegin(v), std::rbegin(v) + a
#define rall3(v, a, b) std::rbegin(v) + a, std::rbegin(v) + b
#define rall(...) overload3(__VA_ARGS__, rall3, rall2, rall1)(__VA_ARGS__)
#define elif else if
#define updiv(N, X) (((N) + (X) - 1) / (X))
#define sigma(a, b) (((a) + (b)) * ((b) - (a) + 1) / 2)
#define INT(...)     \
    int __VA_ARGS__; \
    scan(__VA_ARGS__)
#define LL(...)     \
    ll __VA_ARGS__; \
    scan(__VA_ARGS__)
#define STR(...)        \
    string __VA_ARGS__; \
    scan(__VA_ARGS__)
#define CHR(...)      \
    char __VA_ARGS__; \
    scan(__VA_ARGS__)
#define DOU(...)        \
    double __VA_ARGS__; \
    scan(__VA_ARGS__)
#define LD(...)     \
    ld __VA_ARGS__; \
    scan(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#line 3 "template/alias.hpp"

using ll = long long;
using ld = long double;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
constexpr int inf = 1 << 30;
constexpr ll INF = 1LL << 60;
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int mod = 998244353;
constexpr int MOD = 1e9 + 7;
#line 3 "template/func.hpp"

template <typename T>
inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template <typename T>
inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }
template <typename T, typename U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}
template <typename T, typename U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto it = std::begin(v); it != std::end(v);) {
        os << *it << ((++it) != std::end(v) ? " " : "");
    }
    return os;
}
template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &in : v) {
        is >> in;
    }
    return is;
}
inline void scan() {}
template <class Head, class... Tail>
inline void scan(Head &head, Tail &...tail) {
    std::cin >> head;
    scan(tail...);
}
template <class T>
inline void print(const T &t) { std::cout << t << '\n'; }
template <class Head, class... Tail>
inline void print(const Head &head, const Tail &...tail) {
    std::cout << head << ' ';
    print(tail...);
}
template <class... T>
inline void fin(const T &...a) {
    print(a...);
    exit(0);
}
#line 3 "template/util.hpp"

struct IOSetup {
    IOSetup() {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
        std::cout.tie(0);
        std::cout << std::fixed << std::setprecision(12);
        std::cerr << std::fixed << std::setprecision(12);
    }
} IOSetup;
#line 3 "template/debug.hpp"

#ifdef LOCAL
#include <dump.hpp>
#else
#define debug(...)
#endif
#line 8 "template/template.hpp"
using namespace std;
#line 3 "graph/flow/ford-fullkerson.hpp"

// edge class (for network-flow)
template<class FLOWTYPE> struct FlowEdge {
    // core members
    int rev, from, to;
    FLOWTYPE cap, icap, flow;
    
    // constructor
    FlowEdge(int r, int f, int t, FLOWTYPE c)
    : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {}
    void reset() { cap = icap, flow = 0; }
    
    // debug
    friend ostream& operator << (ostream& s, const FlowEdge& E) {
        return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
    }
};

// graph class (for network-flow)
template<class FLOWTYPE> struct FlowGraph {
    // core members
    vector<vector<FlowEdge<FLOWTYPE>>> list;
    vector<pair<int,int>> pos;  // pos[i] := {vertex, order of list[vertex]} of i-th edge
    
    // constructor
    FlowGraph(int n = 0) : list(n) { }
    void init(int n = 0) {
        list.assign(n, FlowEdge<FLOWTYPE>());
        pos.clear();
    }
    
    // getter
    vector<FlowEdge<FLOWTYPE>> &operator [] (int i) {
        return list[i];
    }
    const vector<FlowEdge<FLOWTYPE>> &operator [] (int i) const {
        return list[i];
    }
    size_t size() const {
        return list.size();
    }
    FlowEdge<FLOWTYPE> &get_rev_edge(const FlowEdge<FLOWTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    FlowEdge<FLOWTYPE> &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const FlowEdge<FLOWTYPE> &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<FlowEdge<FLOWTYPE>> get_edges() const {
        vector<FlowEdge<FLOWTYPE>> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    
    // change edges
    void reset() {
        for (int i = 0; i < (int)list.size(); ++i) {
            for (FlowEdge<FLOWTYPE> &e : list[i]) e.reset();
        }
    }
    void change_edge(FlowEdge<FLOWTYPE> &e, FLOWTYPE new_cap, FLOWTYPE new_flow) {
        FlowEdge<FLOWTYPE> &re = get_rev_edge(e);
        e.cap = new_cap - new_flow, e.icap = new_cap, e.flow = new_flow;
        re.cap = new_flow;
    }
    
    // add_edge
    void add_edge(int from, int to, FLOWTYPE cap) {
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(FlowEdge<FLOWTYPE>((int)list[to].size(), from, to, cap));
        list[to].push_back(FlowEdge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0));
    }

    // debug
    friend ostream& operator << (ostream& s, const FlowGraph &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }
};

// Ford-Fulkerson
template<class FLOWTYPE> FLOWTYPE FordFulkerson
 (FlowGraph<FLOWTYPE> &G, int s, int t, FLOWTYPE limit_flow)
{
    FLOWTYPE current_flow = 0;
    
    // DFS
    vector<bool> used((int)G.size(), false);
    auto dfs = [&](auto self, int v, FLOWTYPE up_flow) {
        if (v == t) return up_flow;
        FLOWTYPE res_flow = 0;
        used[v] = true;
        for (FlowEdge<FLOWTYPE> &e : G[v]) {
            if (used[e.to] || e.cap == 0) continue;
            FLOWTYPE flow = self(self, e.to, min(up_flow - res_flow, e.cap));
            FlowEdge<FLOWTYPE> &re = G.get_rev_edge(e);
            if (flow <= 0) continue;
            res_flow += flow;
            e.cap -= flow, e.flow += flow;
            re.cap += flow, re.flow -= flow;
            if (res_flow == up_flow) break;
        }
        return res_flow;
    };
    
    // flow
    while (current_flow < limit_flow) {
        used.assign((int)G.size(), false);
        FLOWTYPE flow = dfs(dfs, s, limit_flow - current_flow);
        if (!flow) break;
        current_flow += flow;
    }
    return current_flow;
};

template<class FLOWTYPE> FLOWTYPE FordFulkerson(FlowGraph<FLOWTYPE> &G, int s, int t) {
    return FordFulkerson(G, s, t, numeric_limits<FLOWTYPE>::max());
}
#line 5 "test/AOJ/GRL_7_A.test.cpp"

int main() {
    INT(X, Y, E);
    Graph<int> G(X + Y + 2);
    for (int i = 0; i < X; i++) {
        G.addedge(0, i + 1, 1);
    }
    for (int i = 0; i < E; i++) {
        INT(x, y);
        x++;
        y += X + 1;
        G.addedge(x, y, 1);
    }
    for (int i = 0; i < Y; i++) {
        G.add_undirected_edge(i + X + 1, X + Y + 1, 1);
    }
    FordFulkerson<int> ff;
    cout << ff.solve(G, 0, X + Y + 1) << endl;
}