又是某位捧油問我的問題，用 Messenger 傳太慢了，直接打成一篇 blog 好了= = 別再給我增加工作量啊垃圾 我還要把舊站的文章搬過來改成 md 檔啊 = =

題目

我先附上連結

題目敘述大意就是有兩個部門因為要搜查之類的，所以兩兩配對成一個「小組」 不過並沒有規定同一人只能屬於一個小組，同一名警察可以同時屬於複數的小組

有了小組就要管理，要管理就要組長，因此局長決定要選出其中一些人當組長 組長會有比較好的待遇，但是這些待遇會造成財政負擔，所以希望組長盡可能地少，但是對於任何一個小組至少有一個組長

注意：至少有一個 $\to$ 有兩個也沒關係

這超重要啊！我當初以為一組只能有一個所以很順手的寫了個著色，結果這題根本不能用著色寫 （但是不小心撈到73分，我問號）

解法

很顯然的要先轉成一張圖，這絕對是圖論 = = 也就是說題意可以被化簡成這樣： 給定一張圖，求至少需要選幾個節點才能保證所有邊都有被這些點接觸到 。。。啊不就匈牙利 既然知道是匈牙利就好寫啦，不知道匈牙利的可以翻一下這篇 然後因為這篇有不少內容，所以請自己 ctrl + F（Mac用戶請用 cmd + F）搜尋一下匈牙利演算法

因為這題真的是裸題（？）所以我就直接附 code 了

code

// by. MiohitoKiri5474
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

#define maxN 200005

vector < int > edges[maxN];
int match[maxN], visit[maxN], turn;

inline bool dfs ( int n ){
    visit[n] = turn;
    for ( auto i: edges[n] ){
        if ( match[i] == -1 || ( visit[match[i]] != turn && dfs ( match[i] ) ) ){
            match[i] = n;
            match[n] = i;
            return true;
        }
    }

    return false;
}

int main(){
    ios::sync_with_stdio ( false );
    cin.tie ( 0 );
    cout.tie ( 0 );

    int t, m, u, v, p, q, ans;
    cin >> t;
    while ( t-- ){
        ans = 0;
        memset ( match, -1, sizeof match );
        for ( auto &i: edges )
            i.clear();
        cin >> p >> q >> m;
        while ( m-- ){
            cin >> u >> v;
            v += p;
            edges[u].pb ( v );
            edges[v].pb ( u );
        }

        p += q;
        for ( int i = 0 ; i <= p ; i++ ){
            if ( match[i] == -1 ){
                turn++;
                // 省去每次 dfs 都要 memset 一次 visit 陣列的時間
                if ( dfs ( i ) )
                    ans++;
                    // 如果可以找到新的配對就 ans++
            }
        }

        cout << ans << '\n';
    }
}

tips

然後這邊我有用到一個小技巧，可以避免 TLE 通常在 dfs 一份有環圖時，都會開一個 bool 陣列記錄這個點是否已經處理過了，避免在這邊一直繞造成 stack overflow 不過在需要 dfs 數次的時候就需要把這個陣列 memset，需要浪費 $O ( N )$ 的時間（我不是很確定） 如果我們把這個陣列開成 int 陣列 並且在dfs時不是確認 $visit[n] == true$ 而是確認 $visit[n] == turn$，每到下一輪就把 $turn++$，以便紀錄這是底幾輪 這樣就不用浪費時間去 memset 了