POJ 2594 Treasure Exploration (Floyd+最小路径覆盖)

题目大意：

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

解题分析：

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

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 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-Hungary());
46     }
47 }

2018-11-15