poj 1422

题意：一个城市里的路都是单向的，这些路不构成环，每个交点都只属于一条路径。伞兵可以在任意一个交点着陆，问最少要多少个伞兵才能把所有交点都访问到？

分析：这是一个最小路径覆盖问题。最小路径覆盖数＝顶点数－最大匹配。至于公式是如何证明的，还是似懂非懂。参考资料：http://hi.baidu.com/oksbqoyifkbfirq/item/ebfe96c8a85f7844a9ba94b0

View Code

 1 #include<cstdio>
 2 int mat[2][500];
 3 bool visited[500],matrix[500][500];
 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 int main()
39 {
40     int i,j,t,a,b;
41     scanf("%d",&t);
42     while(t--)
43     {
44         scanf("%d%d",&nx,&k);
45         ny=nx;
46         for(i=1;i<=nx;i++)
47         {
48             for(j=1;j<=ny;j++)
49                 matrix[i][j]=false;
50         }
51         for(i=1;i<=k;i++)
52         {
53             scanf("%d%d",&a,&b);
54             matrix[a][b]=true;
55         }
56         printf("%d\n",nx-Hungary());
57     }
58     return 0;
59 }