poj2594 （最小路径覆盖 + floyd）

题目链接  http://poj.org/problem?id=2594)

题目大意：

一个有向图中， 有若干条连接的路线， 问最少放多少个机器人，可以将整个图上的点都走过。 最小路径覆盖问题。

分析：

这时最小路径覆盖问题， 最小路径覆盖 = |V| - 最大匹配数。 （有关最小路径覆盖，最大匹配问题，相关概念不懂得 点这里） 当然做这道题还有一个坑！！ 如果有向图的边有相交的情况，那么就不能简单的对原图求二分匹配了 详细讲解看这。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string.h>

#include<cstring>

using namespace std;

int n, m, sum, ans[], v[], map[][];

void floyd()  // 求图的闭包

{

    for(int k = ; k <= n; k++)

    {

        for(int i = ; i <= n; i++)

        {

            if(map[i][k] == )

            {

                for(int j = ; j <= n; j++)

                {

                    if(map[k][j] == )

                        map[i][j] = ;

                }

            }

        }

    }

}

int dfs(int x) // 找增广路径

{

    for(int i = ; i <= n; i++)

    {

        if(map[x][i] ==  && v[i] == )

        {

            v[i] = ;

            if(ans[i] ==  || (ans[i] !=  && dfs(ans[i]) == ))

            {

                ans[i] = x;

                return ;

            }

        }

    }

    return ;

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF && (n || m))

    {

        memset(ans, , sizeof(ans));

        memset(map, , sizeof(map));

        for(int i = ; i <= m; i++)

        {

            int x, y;

            scanf("%d%d", &x, &y);

            map[x][y] = ;

        }

        floyd();

        sum = ;

        for(int i = ; i <= n; i++) // 求最大匹配

        {

            memset(v, , sizeof(v));

            int t = dfs(i);

            if(t == )

                sum++;

        }

        printf("%d\n", n - sum);

    }

    return ;

}