hdu 2594

题意：N个星球之间存在M条单向通道（不构成圈），同一个星球可能出现在两条不同的路径中。现用若干个机器人走遍所有星球，每个机器人的起点任意，最少要多少个机器人？

分析：这是poj1422的升级版，在有交叉的情况下，标准的最小路径覆盖不适用（例如：1→2，2→3，4→2，2→5，当有了（1，2），（2，3）这个匹配时，2就被删去了，算出的答案是3，而这种情况答案应是2），所以要加一个floyd，求出各顶点的可达矩阵。

View Code

 1 #include<cstdio>
 2 int mat[2][501];
 3 bool visited[501],matrix[501][501];
 4 int nx,ny,k;
 5 int path(int u)
 6 {
 7     int i;
 8     for(i=1;i<=ny;i++)
 9     {
10         if(matrix[u][i] && !visited[i])
11         {
12             visited[i]=true;
13             if(mat[1][i]==-1 || path(mat[1][i]))
14             {
15                 mat[0][u]=i;
16                 mat[1][i]=u;
17                 return 1;
18             }
19         }
20     }
21     return 0;
22 }
23 int Hungary()
24 {
25     int ans=0,i,j;
26     for(i=1;i<=nx;i++)
27         mat[0][i]=-1;
28     for(i=1;i<=ny;i++)
29         mat[1][i]=-1;
30     for(i=1;i<=nx;i++)
31     {
32         for(j=1;j<=ny;j++)
33             visited[j]=false;
34         ans+=path(i);
35     }
36     return ans;
37 }
38 void floyd()
39 {
40     int i,j,k;
41     for(k=1;k<=nx;k++)
42     {
43         for(i=1;i<=nx;i++)
44         {
45             for(j=1;j<=nx;j++)
46             {
47                 if(matrix[i][k] && matrix[k][j])
48                     matrix[i][j]=true;
49             }
50         }
51     }
52 }
53 int main()
54 {
55     int k;
56     while(scanf("%d%d",&nx,&k) && (nx||k))
57     {
58         int i,j;
59         ny=nx;
60         for(i=1;i<=nx;i++)
61         {
62             for(j=1;j<=ny;j++)
63                 matrix[i][j]=false;
64         }
65         int a,b;
66         for(i=1;i<=k;i++)
67         {
68             scanf("%d%d",&a,&b);
69             matrix[a][b]=true;
70         }
71         floyd();
72         printf("%d\n",nx-Hungary());
73     }
74     return 0;
75 }