POJ 2594 Treasure Exploration（最小路徑覆寫 傳遞閉包）

最小路徑覆寫 == 頂點數 - 配對數，此時每個頂點隻能經過一次，若是經過一個點多次，例如下面部落格所介紹的，當路徑相交的時候，應該進行一次傳遞閉包處理，也就是跑一遍Floyd再進行最大比對

講解部落格：http://www.cnblogs.com/ka200812/archive/2011/07/31/2122641.html

題目連結：https://vjudge.net/problem/POJ-2594

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 505;
int boy[maxn];//記錄被選着的編号
bool vis[maxn];
int g[maxn][maxn];
int n, m, k;
int dfs(int u)
{
    for(int i = 1; i <= n; i ++)//枚舉被選者
    {
        if(g[u][i] && ! vis[i])
        {
            vis[i] = 1;
            if(boy[i] == 0 || dfs(boy[i]))
            {
                boy[i] = u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF && (n + m))
    {
        memset(boy, 0, sizeof(boy));
        memset(vis, 0, sizeof(vis));
        memset(g, 0, sizeof(g));
        int u, v;
        for(int i = 1; i <= m; i ++)
        {
            scanf("%d%d", &u, &v);
            g[u][v] = 1;
        }
        for(int k = 1; k <= n; k ++)
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= n; j ++)
                    if(g[i][k] && g[k][j])
                        g[i][j] = 1;
        int ans = 0;
        for(int i = 1; i <= n; i ++)
        {
            memset(vis, 0, sizeof(vis));
            if(dfs(i)) ans ++;
        }
        printf("%d\n", n - ans);
    }
    return 0;
}