【題解】ZeroJudge c455: 4. 警力配置

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int t, p, q, k, a, b, y[100005], vis[100005], ans, turn;
vector <int> v[100005];

bool dfs(int x){
    for (auto i:v[x]){
        if (!y[i]){
            y[i] = x;
            return 1;
        }
        else if (vis[y[i]] != turn){
            vis[y[i]] = turn;
            if (dfs(y[i])){
                y[i] = x;
                return 1;
            }
        }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--){
        cin >> p >> q >> k;
        for (int i = 1; i <= p; i++){
            v[i].clear();
        }
        for (int i = 0; i < k; i++){
            cin >> a >> b;
            v[a].push_back(b);
        }
        memset(y, 0, sizeof(y));
        ans = 0;
        for (int i = 1; i <= p; i++){
            turn = i;
            if (dfs(i)) ans++;
        }
        cout << ans << "\n";
    }
}