[最小径径覆盖]poj 2594：Treasure Exploration

[最小路径覆盖]poj 2594：Treasure Exploration

大致题意：

    给出一个由n个顶点m条边组成的无回路有向图。求最少可以同时存在多少路径，使得这些路径可以覆盖所有的点(注：每个都点可以被多条路径覆盖)。

 

大致思路:
    最小路径覆盖的一点小小变形，由于这里的点可以被重复覆盖，所以除了按照普通求最小路径覆盖的方式建立二分图以外，还要对原图用floyd求一遍传递闭包，并更新二分图。接下来用点数n减去最大匹配得到的就是答案。

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000;
int c,d;
int map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];

int dfs(int s){
    for(int i=1;i<=d;i++){
        if(!vis[i]&&map[s][i]){
            vis[i]=1;
            if(linkk[i]==-1||dfs(linkk[i])){
                linkk[i]=s;
                return 1;
            }
        }
    }
    return 0;
}

void floyd(int n){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(map[i][k]&&map[k][j]){
                    map[i][j]=1;
                }
            }
        }
    }
}
int main(){
    int n,m,a,b,ans,i,j;
    while(scanf("%d%d",&n,&m)&&(n||m)){
        c=d=n;
        ans=0;
        memset(map,0,sizeof(map));
        while(m--){
            scanf("%d%d",&a,&b);
            map[a][b]=1;
        }
        floyd(n);
        memset(linkk,-1,sizeof(linkk));
        for(i=1;i<=c;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans);
    }
    return 0;
}