<题目链接>
题目大意：
机器人探索宝藏，有N个点，M条边。问你要几个机器人才能遍历所有的点。
解题分析：
刚开始还以为是最小路径覆盖的模板题，但是后面才知道，本题允许一个点经过多次，这与最小路径覆盖中，路径之间不能有交点重合相矛盾，所以，我们用Floyd利用传递闭包对原图进行一些处理。所谓传递闭包就是，a能到b，b能到c，所以a能到c。最后对处理后的图计算最小路径覆盖。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N =;
int n,m;
int g[N][N],vis[N],match[N];
bool dfs(int x){
for(int i=;i<=n;i++){
if(g[x][i]&&!vis[i]){
vis[i]=;
if(match[i]==-||dfs(match[i])){
match[i]=x;
return true;
}
}
}
return false;
}
int Hungary(){
int ans=;
memset(match,-,sizeof(match));
for(int i=;i<=n;i++){
memset(vis,,sizeof(vis));
ans+=dfs(i);
}
return ans;
}
void Floyd(){ //Floyd传递闭包
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
if(g[i][k]&&g[k][j])
g[i][j]=;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF,n||m){
memset(g,,sizeof(g));
for(int i=;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
g[u][v]=;
}
Floyd();
printf("%d\n",n-Hungary());
}
}
2018-11-15