题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1151
题目大意：
城镇之间互相有边，但都是单向的，并且不会构成环，现在派伞兵降落去遍历城镇，问最少最少派多少人去
思路：
转化题意，求用最少的有向边覆盖点 --------> 最小边覆盖数目=顶点数-最大二分匹配数目
注意：这道题目中说得是有向无环的DAG，所以顶点数目不能按照2倍来计算
在DAG中我们假设点集为 -----> Ni 然后建立每个点对应的虚点 ------>Ni'
那么在二分匹配的时候绝对不会出现 N1---->N2' N2---->N1' 这样的情况，这样的就构成了环状
所以在DAG中求取最小边覆盖，点数不用加倍
代码：
1 #include <stdio.h> 2 #include <string.h> 3 int g[125][125],vis[125],who[125]; 4 int n; 5 bool find(int x) { 6 for(int i=1; i<=n; ++i) { 7 if(g[x][i]&&!vis[i]) { 8 vis[i]=1; 9 if(!who[i]||find(who[i])) { 10 who[i]=x; 11 return true; 12 } 13 } 14 } 15 return false; 16 } 17 int main() { 18 int t; 19 scanf("%d",&t); 20 while(t--) { 21 memset(g,0,sizeof(g)); 22 memset(who,0,sizeof(who)); 23 int m,u,v; 24 scanf("%d",&n); 25 scanf("%d",&m); 26 while(m--) { 27 scanf("%d %d",&u,&v); 28 g[u][v]=1; 29 } 30 int sum=0; 31 for(int i=1; i<=n; ++i) { 32 memset(vis,0,sizeof(vis)); 33 if(find(i)) sum++; 34 } 35 printf("%d ",n-sum); 36 } 37 return 0; 38 }