【題解】TIOJ 2037 警力配置

【題目敘述】https://tioj.ck.tp.edu.tw/problems/2037

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

int T, p, q, k, x, y, m[100005], vis[100005], ans;
vector <int> v[100005], c;

bool f(int x){
    vis[x] = 1;
    c.push_back(x);
    for (auto &i:v[x]){
        if (!m[i]){
            m[i] = x;
            return 1;
        }
        if (vis[m[i]]) continue;
        if (f(m[i])){
            m[i] = x;
            return 1;
        }
    }
    return 0;
}

int main(){
    cin >> T;
    while (T--){
        cin >> p >> q >> k;
        for (int i = 1; i <= p; i++){
            v[i].clear();
        }
        for (int i = 1; i <= q; i++){
            m[i] = 0;
        }
        for (int i = 1; i <= k; i++){
            cin >> x >> y;
            v[x].push_back(y);
        }
        ans = 0;
        for (int i = 1; i <= p; i++){
            if (f(i)) ans++;
            while (c.size()){
                vis[c.back()] = 0;
                c.pop_back();
            }
        }
        cout << ans << "\n";
    }
}
分享本文 Share with friends