HDOJ1151解题报告【有向图的最小路径覆盖】

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1151

题目概述：

　　一座城市有n个路口和m条有向路径，题目保证没有环，现在派一些伞兵去巡查城市，求最少需要多少伞兵才能走遍所有路口。

大致思路：

　　刚开始的时候是有些懵逼的，后来看了一下网上大神的题解，发现这个题是求DAG的最小路径覆盖，就等于顶点数-最大匹配数。

　　将DAG转化为二分图的方法是如果有一条p->q的边，那么在二分图中加入p-q之间的无向边，其中p在集合S，q在集合T。

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <vector>
 6 #include <ctime>
 7 #include <map>
 8 #include <queue>
 9 #include <cstring>
10 #include <algorithm>
11 using namespace std;
12 
13 #define sacnf scanf
14 #define scnaf scanf
15 #define maxn 310
16 #define maxm 26
17 #define inf 1061109567
18 #define Eps 0.00001
19 const double PI=acos(-1.0);
20 #define mod 7
21 #define MAXNUM 10000
22 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
23 double Abs(double x) {return (x<0)?-x:x;}
24 typedef long long ll;
25 typedef unsigned int uint;
26 
27 int n,m;
28 vector<int> G[maxn];
29 int vis[maxn],l[maxn];
30 
31 bool dfs(int u)
32 {
33     int len=G[u].size();
34     for(int i=0;i<len;i++)
35     {
36         int v=G[u][i];
37         if(!vis[v])
38         {
39             vis[v]=1;
40             if(l[v]==-1||dfs(l[v]))
41             {
42                 l[v]=u;return true;
43             }
44         }
45     }
46     return false;
47 }
48 
49 int hungary()
50 {
51     int cnt=0;
52     memset(l,-1,sizeof(l));
53     for(int i=1;i<=n;i++)
54     {
55         memset(vis,0,sizeof(vis));
56         if(dfs(i)) cnt++;
57     }
58     return cnt;
59 }
60 
61 int main()
62 {
63     //freopen("data.in","r",stdin);
64     //freopen("data.out","w",stdout);
65     //clock_t st=clock();
66     int T,a,b;scnaf("%d",&T);
67     while(T--)
68     {
69         scanf("%d%d",&n,&m);
70         for(int i=1;i<=n*2;i++) G[i].clear();
71         for(int i=1;i<=m;i++)
72         {
73             scanf("%d%d",&a,&b);
74             G[a].push_back(n+b);
75             G[n+b].push_back(a);
76         }
77         int ans=hungary();
78         printf("%d
",n-ans);
79     }
80     //clock_t ed=clock();
81     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
82     return 0;
83 }