poj2594 （最小路径覆盖 + floyd）

迷南。 2022-01-10 05:41 233阅读 0赞

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

题目大意：

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

分析：

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

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string.h>
    #include<cstring>
    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", n - sum);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/wd-one/p/4547741.html

[http_poj.org_problem_id_2594]: http://poj.org/problem?id=2594
[Link 1]: http://www.cnblogs.com/wd-one/p/4547616.html
[Link 2]: http://www.cnblogs.com/ka200812/archive/2011/07/31/2122641.html