poj2594 （最小路徑覆蓋 + floyd）

poj2594 （最小路徑覆蓋 + floyd）

題目大意：
一個有向圖中， 有若干條連接的路線， 問最少放多少個機器人，可以將整個圖上的點都走過。 最小路徑覆蓋問題。

分析：
這時最小路徑覆蓋問題， 最小路徑覆蓋 = |V| - 最大匹配數。 （有關最小路徑覆蓋，最大匹配問題，相關概念不懂得點這裡） 當然做這道題還有一個坑！！ 如果有向圖的邊有相交的情況，那麼就不能簡單的對原圖求二分匹配了 詳細講解看這

#include
#include
#include
#include
#include
using namespace std;

int n, m, sum, ans[505], v[505], map[505][505];
void floyd()  // 求圖的閉包
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            if(map[i][k] == 1)
            {
                for(int j = 1; j <= n; j++)
                {
                    if(map[k][j] == 1)
                        map[i][j] = 1;
                }
            }
        }
    }
}

int dfs(int x) // 找增廣路徑
{
    for(int i = 1; i <= n; i++)
    {
        if(map[x][i] == 1 && v[i] == 0)
        {
            v[i] = 1;
            if(ans[i] == 0 || (ans[i] != 0 && dfs(ans[i]) == 1))
            {
                ans[i] = x;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    while(scanf(%d%d, &n, &m) != EOF && (n || m))
    {
        memset(ans, 0, sizeof(ans));
        memset(map, 0, sizeof(map));
        for(int i = 1; i <= m; i++)
        {
            int x, y;
            scanf(%d%d, &x, &y);
            map[x][y] = 1;
        }

        floyd();

        sum = 0;
        for(int i = 1; i <= n; i++) // 求最大匹配
        {
            memset(v, 0, sizeof(v));
            int t = dfs(i);
            if(t == 1)
                sum++;
        }
        printf(%d
, n - sum);
    }
    return 0;
}