POJ-2594 Treasure Exploration，floyd+最小路径覆盖！

复见此题，时隔久远，已忘，悲矣！

题意：用最少的机器人沿单向边走完（覆盖）全部的点。典型的最小路径覆盖，如果不懂二分图匹配可以参考：二分图大讲堂先用floyd传递闭包，再求最大匹配，最小路径覆盖=V-最大二分匹配（最小点覆盖）。为什么要用floyd传递闭包呢，每个点可以被多个机器人走过，博主就是这里没考虑到。。

我记得这个题是写过博客的。。。。//领接矩阵匈牙利算法。无重边无环。。。。。。

检查博客发现以前果然写过这个题的题解。。。

const int N=1e3+10;

int n,m,g[N][N],used[N],linked[N];

void floyd()

{

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

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

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

        g[i][j]=max(g[i][j],min(g[i][k],g[k][j]));

}

bool dfs(int u)

{

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

        if(g[u][i]&&!used[i])

        {

            used[i]=1;

            if(linked[i]==-1||dfs(linked[i]))

            {

                linked[i]=u;

                return 1;

            }

        }

    return 0;

}

int hungary()

{

    int ans=0;

    memset(linked,-1,sizeof(linked));

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

    {

        memset(used,0,sizeof(used));

        if(dfs(i)) ans++;

    }

    return n-ans;

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        if(m==n&&n==0) return 0;

        memset(g,0,sizeof(g));

        int u,v;

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

        {

            scanf("%d%d",&u,&v);

            g[u][v]=1;

        }

        floyd();

        printf("%d\n",hungary());

    }

    return 0;

}

巴特西

POJ-2594 Treasure Exploration，floyd+最小路径覆盖！

最新文章

热门文章