一个星球上有很多点，点与点之间有很多单向路
问可重点的最小路径覆盖
利用floyd缩点后求二分图最大匹配
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 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-ans); 57 } 58 } 59