P1010

本来该使用 Hopcroft 算法的，最终写了 Dinic，Hopcroft 算法有时间再来补吧

#include <bits/stdc++.h>
using i64 = long long;

const int N = 20010, M = (1000010 + N) << 1;
const i64 INF = 0x3f3f3f3f3f3f3f3f;
int T;
int n, m, s, t;
int head[N], to[M], cap[M], nxt[M], idx = 0;
int dep[N], cur[N];

void add(int u, int v, int c)
{
    to[idx] = v;
    cap[idx] = c;
    nxt[idx] = head[u];
    head[u] = idx; ++ idx; return;
}
void biadd(int u, int v, int c)
{
    add(u, v, c), add(v, u, 0);
    return;
}
std::queue<int> q;
bool bfsearch(void)
{
    q = std::queue<int>();
    for (int i = 1; i <= n + m + 2; ++ i) {
        dep[i] = -1;
    }
    dep[s] = 0, cur[s] = head[s], q.push(s);

    while (!q.empty())
    {
        int fro = q.front(); q.pop();
        for (int i = head[fro]; i != -1; i = nxt[i])
        {
            int e = to[i];
            if (dep[e] == -1 && cap[i])
            {
                cur[e] = head[e];
                dep[e] = dep[fro] + 1;
                if (e == t) return true;
                q.push(e);
            }
        }
    }
    return false;
}
i64 extraRoad(int u, i64 lim)
{
    if (u == t) return lim;
    i64 flow = 0;
    for (int i = cur[u]; i != -1 && flow < lim; i = nxt[i])
    {
        cur[u] = i; int e = to[i];
        if (dep[e] == dep[u] + 1 && cap[i])
        {
            int del = extraRoad(e, std::min(1ll * cap[i], lim - flow));
            if (!del) dep[e] = -1;
            flow += del, cap[i] -= del, cap[i xor 1] += del;
        }
    }
    return flow;
}
i64 Dinic(void)
{
    i64 res = 0, flow;
    while (bfsearch())
        while (flow = extraRoad(s, INF))
            res += flow;
    return res;
}

int main(void)
{
    scanf("%d", &T);
    while (T --) {
        int e, inpu, inpv;
        scanf("%d%d%d", &n, &m, &e);

        for (int i = 1; i <= n + m + 2; ++ i) {
            head[i] = -1;
        }
        idx = 0;

        s = n + m + 1, t = n + m + 2;
        for (int i = 1; i <= e; ++ i) {
            scanf("%d%d", &inpu, &inpv);
            biadd(inpu, n + inpv, 1);
        }
        for (int i = 1; i <= n; ++ i) {
            biadd(s, i, 1);
        }
        for (int i = n + 1; i <= n + m; ++ i) {
            biadd(i, t, 1);
        }
        printf("%lld\n", Dinic());
    }
    return 0;
}