<>

题目大意：

机器人探索宝藏，有N个点，M条边。问你要几个机器人才能遍历所有的点。 

解题分析：

刚开始还以为是最小路径覆盖的模板题，但是后面才知道，本题允许一个点经过多次，这与最小路径覆盖中，路径之间不能有交点重合相矛盾，所以，我们用Floyd利用传递闭包对原图进行一些处理。所谓传递闭包就是，a能到b，b能到c，所以a能到c。最后对处理后的图计算最小路径覆盖。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int N =505; 7 int n,m; 8 int g[N][N],vis[N],match[N]; 9 bool dfs(int x){10     for(int i=1;i<=n;i++){11         if(g[x][i]&&!vis[i]){12             vis[i]=1;13             if(match[i]==-1||dfs(match[i])){14                 match[i]=x;15                 return true;16             }17         }18     }19     return false;20 }21 int Hungary(){22     int ans=0;23     memset(match,-1,sizeof(match));24     for(int i=1;i<=n;i++){25         memset(vis,0,sizeof(vis));26         ans+=dfs(i);27     }28     return ans;29 }30 void Floyd(){     //Floyd传递闭包31     for(int k=1;k<=n;k++)32         for(int i=1;i<=n;i++)33             for(int j=1;j<=n;j++)34                 if(g[i][k]&&g[k][j])35                     g[i][j]=1;36 }37 int main(){38     while(scanf("%d%d",&n,&m)!=EOF,n||m){39         memset(g,0,sizeof(g));40         for(int i=1;i<=m;i++){41             int u,v;scanf("%d%d",&u,&v);42             g[u][v]=1;    43         }44         Floyd();45         printf("%d\n",n-Hungary());46     }47 }
       
      
     

 

 

2018-11-15