最大フローの基礎と二部マッチングへの応用

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    long long cap;
    int rev;
};

struct FordFulkerson {
    int N;
    vector<vector<Edge>> G;
    vector<bool> used;

    FordFulkerson(int N) : N(N), G(N), used(N) {}

    void add_edge(int from, int to, long long cap) {
        G[from].push_back({to, cap, (int)G[to].size()});
        G[to].push_back({from, 0, (int)G[from].size() - 1});
    }

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        used[v] = true;
        for (auto &e : G[v]) {
            if (!used[e.to] && e.cap > 0) {
                long long 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;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (true) {
            fill(used.begin(), used.end(), false);
            long long f = dfs(s, t, LLONG_MAX);
            if (f == 0) break;
            flow += f;
        }
        return flow;
    }
};

#include <bits/stdc++.h>
using namespace std;

struct Dinic {
    struct Edge {
        int to;
        long long cap;
        int rev;
    };

    int N;
    vector<vector<Edge>> G;
    vector<int> level, prog;

    Dinic(int N) : N(N), G(N), level(N), prog(N) {}

    void add_edge(int fr, int to, long long cap) {
        G[fr].push_back({to, cap, (int)G[to].size()});
        G[to].push_back({fr, 0, (int)G[fr].size() - 1});
    }

    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto &e : G[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int &i = prog[v]; i < G[v].size(); i++) {
            auto &e = G[v][i];
            if (e.cap <= 0 || level[e.to] != level[v] + 1) continue;
            long long ret = dfs(e.to, t, min(f, e.cap));
            if (ret > 0) {
                e.cap -= ret;
                G[e.to][e.rev].cap += ret;
                return ret;
            }
        }
        return 0;
    }

    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(prog.begin(), prog.end(), 0);
            long long f;
            while ((f = dfs(s, t, LLONG_MAX)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
};

int main() {
    int L = 3;
    int R = 3;

    int s = L + R;
    int t = s + 1;

    Dinic mf(L + R + 2);

    for (int i = 0; i < L; i++) {
        mf.add_edge(s, i, 1);
    }

    for (int i = 0; i < R; i++) {
        mf.add_edge(L + i, t, 1);
    }

    mf.add_edge(0, L + 0, 1);
    mf.add_edge(0, L + 1, 1);
    mf.add_edge(1, L + 1, 1);
    mf.add_edge(2, L + 2, 1);

    cout << mf.max_flow(s, t) << endl;
}