题目链接:http://poj.org/problem?id=2594
题意是有n个点,m条单向边,然后在边上放机器人,问最少放多少个机器人能遍历到所有的点。
看似是一道裸的最小路径覆盖问题,但是会有一种单向边相交的情况看下图
这种情况直接跑最大匹配数会得到2,然后求得最小路径覆盖值为3,其实这个图就是A->E,B->D,直接看出最小路径覆盖数是2,所以这里我们需要对这个有交点的情况跑一遍闭包传递(Floyd),这样就会增加四条边:A->E,B->E,B->D,A->D,然后再去求最小路径覆盖就好了。
AC代码:
// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define maxn 605
#define maxm 6005
using namespace std;
struct Node{
int to,next;
}Edge[maxm];
int a[maxn][maxn];
int head[maxm],num;
int pre[maxn];
bool vis[maxn];
int T,n,m;
void init(){
memset(head,-1,sizeof(head));
memset(a,0,sizeof(a));
num = 0;
}
void add(int u,int v){
Edge[num].to = v;
Edge[num].next = head[u];
head[u] = num ++;
}
void Floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
if(a[k][i] == 1){
for(int j=1;j<=n;j++){
if(a[i][j] == 1){
a[k][j] = 1;
}
}
}
}
}
}
bool dfs(int u){
for(int i=head[u];i!=-1;i=Edge[i].next){
int v = Edge[i].to;
if(vis[v] == false){
vis[v] = true;
if(pre[v] == -1 || dfs(pre[v])){
pre[v] = u;
return true;
}
}
}
return false;
}
int solve(){
int sum = 0;
memset(pre,-1,sizeof(pre));
for(int i=1;i<=n;i++){
memset(vis,false,sizeof(vis));
if(dfs(i)) sum ++;
}
return sum;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n == 0 && m == 0) break;
init();
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
a[u][v] = 1;
}
Floyd();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(a[i][j] == 1){
add(i, j);
}
}
}
int ans = solve();
printf("%d\n",n - ans);
}
return 0;
}