一个星球上有很多点，点与点之间有很多单向路

问可重点的最小路径覆盖

利用floyd缩点后求二分图最大匹配

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=505; 6 int m,n; 7 int map[maxn][maxn]; 8 int link[maxn],vis[maxn]; 9 void floyd()10 {11     int i,j,k;12     for(k=1;k<=n;k++)13         for(i=1;i<=n;i++)14             for(j=1;j<=n;j++)15             {16                 if(map[i][k]&&map[k][j])17                     map[i][j]=1;18             }19 }20 bool dfs(int t)21 {22     int i;23     for(i=1;i<=n;++i)24     {25         if(!vis[i]&&map[t][i])26         {27             vis[i]=1;28             if(link[i]==-1||dfs(link[i]))29             {30                 link[i]=t;31                 return 1;32             }33         }34     }35     return 0;36 }37 int main()38 {39     int ans,i,b,a;40     while(~scanf("%d%d",&n,&m)&&(n+m))41     {42         memset(map,0,sizeof(map));43         for(i=1;i<=m;i++) 44         {45             scanf("%d%d",&a,&b);46             map[a][b]=1;47         }48         floyd();49         memset(link,-1,sizeof(link));50         ans=0;51         for(i=1;i<=n;i++)52         {53             memset(vis,0,sizeof(vis));54             if(dfs(i)) ans++;55         }56         printf("%d\n",n-ans);57     }58 }59