题目：
http://acm.hdu.edu.cn/showproblem.php?pid=1151有向无环图的最小路径覆盖
对于每个路口i，拆成i和i'
若存在一条道路从路口i通向路口j，则连边(i,j')
转化成二分图的最大匹配
二分图的匹配中，对于每一个点，只连一条边，与每路口不能有多人访问吻合
对于每个路口，存在一条入边一条出边；若只有入边或者出边表示这是一条路的端点
所以路的数量=（新图总点数-2*最大匹配数）/2=路口数-最大匹配数
用匈牙利算法求最大匹配
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 using namespace std;
6 const int MaxN=1001;
7 const int MaxM=100001;
8
9 int n,m,ans,T;
10 int result[MaxN];
11 bool vis[MaxN];
12 bool a[2*MaxN][2*MaxN];
13
14 void init()
15 {
16 scanf("%d%d",&n,&m);
17 for (int i=0;i<m;i++)
18 {
19 int x,y;
20 scanf("%d%d",&x,&y);
21 x--;
22 y--;
23 a[x][y+n]=1;
24 }
25 }
26
27 bool find(int k)
28 {
29 for (int i=n;i<2*n;i++)
30 {
31 if (a[k][i]==1 && vis[i]==0) //如果节点i与a相邻并且未被查找过
32 {
33 vis[i]=1; //标记i为已查找过
34 if (result[i]==-1 || find(result[i])) //如果i未在前一个匹配M中 或者 i在匹配M中，但是从与i相邻的节点出发可以有增广路
35 {
36 result[i]=k; //记录查找成功记录
37 return 1; //返回查找成功
38 }
39 }
40 }
41 return 0;
42 }
43
44 int main()
45 {
46 for(scanf("%d",&T);T;T--)
47 {
48 ans=0;
49 memset(a,0,sizeof(a));
50 memset(result,-1,sizeof(result));
51 init();
52 for (int i=0;i<n;i++)
53 {
54 memset(vis,0,sizeof(vis)); //清空上次搜索时的标记
55 if (find(i)==1) ans++; //从节点i尝试扩展
56 }
57 printf("%d\n",n-ans);
58 }
59 return 0;
60 }
61