[最小路径覆盖]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;}

?