POJ-2594-Treasure Exploration(二分

Treasure Exploration

题意：

• 在有向无环图中找尽可能少的机器人覆盖所有的点，机器人可以从边的一端移动到另一端(不能向后移动)不同的机器人可以经过同一点

思路：

• 最小可相交路径覆盖就是用最少的路径覆盖所有的点(在一条路径中不能出现相同的节点，不同路径中可以经过相同节点)
  最小可相交路径覆盖==原图总节点数-加边后的最大边匹配

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int edge[550][550];
int vis[550];
int match[550];
int n,m;
void warshell( )//添边(如果节点i到节点j可以到达那么就添加<i,j>)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!edge[i][j])
            {
                for(int k=1;k<=n;k++)
                {
                    if(edge[i][k]&&edge[k][j])
                    {
                        edge[i][j]=1;
                    }
                }
            }
        }
    }
}
int Hungarian(int x)
{
    for(int i=1;i<=n;i++)
    {
        if(!vis[i]&&edge[x][i]==1)
        {
            vis[i]=1;
            if(match[i]==-1||Hungarian(match[i]))
            {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main( )
{
    int x,y;
    while(~scanf("%d%d",&n,&m)&&(n+m))
    {
        memset(edge,0,sizeof(edge));
        memset(match,-1,sizeof(match));
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            edge[x][y]=1;
        }
        warshell( );
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            memset(vis,0,sizeof(vis));
            if(Hungarian(i))
            {
                ans++;
            }
        }
        printf("%d\n",n-ans);
    }
    return 0;
}