DLKKILL

DLKKILL's world

POJ - 2594 - Treasure Exploration (floyd传递闭包+最小路径覆盖)

题目链接:POJ – 2594

题目大意:

有n个点,m个有向边,用机器人探索这些点,机器人可以从任意的一点开始延路径前进,但不可返回。

问最少需要多少个机器人访问到所有的点。

题目分析:

这个题可以转换到图上的最小路径覆盖问题。

引用:

最小路径覆盖(path covering):是“路径” 覆盖“点”,即用尽量少的不相交简单路径覆盖有向无环图G的所有顶点,即每个顶点严格属于一条路径。路径的长度可能为0(单个点)。

最小路径覆盖数=G的点数-最小路径覆盖中的边数。应该使得最小路径覆盖中的边数尽量多,但是又不能让两条边在同一个顶点相交。拆点:将每一个顶点i拆成两个顶点Xi和Yi。然后根据原图中边的信息,从X部往Y部引边。所有边的方向都是由X部到Y部。因此,所转化出的二分图的最大匹配数则是原图G中最小路径覆盖上的边数。因此由最小路径覆盖数=原图G的顶点数-二分图的最大匹配数便可以得解。

因为在这个题中可以沿着路径前进,所以要先进行传递闭包才可以。

给出代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;
const int maxn=510;
int g[maxn][maxn];
int vist[maxn];
int link[maxn];
int n,m;
bool dfs(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!vist[i]&&g[x][i])
        {
            vist[i]=1;
            if(link[i]==0||dfs(link[i]))
            {
                link[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    while(cin>>n>>m)
    {
        memset(vist,0,sizeof(vist));
        memset(g,0,sizeof(g));
        memset(link,0,sizeof(link));
        if(n==0&&m==0)
            break;
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            g[a][b]=1;
        }
        for(int k=1;k<=n;k++)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    if(i!=j&&g[i][k]&&g[k][j])
                    {
                        g[i][j]=1;
                    }
                }
            }
        }
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            memset(vist,0,sizeof(vist));
            if(dfs(i))
                cnt++;
        }
        cout<<n-cnt<<endl;
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注