频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj2594 (最小路径覆盖 + floyd)
2015-06-03 11:33:19         来源:wangdan11111的专栏  
收藏   我要投稿

 

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

分析:
这时最小路径覆盖问题, 最小路径覆盖 = |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;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 路径
上一篇:HDU 1198 Farm Irrigation (并查集优化,构图)
下一篇:uva 10791 Minimum Sum LCM
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站