hdu

http://acm.hdu.edu.cn/showproblem.php?pid=1151

在一个城市里有n个地点和k条道路,道路都是单向的,并且不存在环.(DAG)

现在伞兵需要去n个地点视察,伞兵只能沿着路的方向走,问最少需要多少伞兵。

DAG的最小路径覆盖是指找最小数目的互相不相交的有向路径,满足DAG的所有顶点都被覆盖.

首先给出公式:DAG的最小路径覆盖数=DAG图中的节点数-相应二分图中的最大匹配数.

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <vector>
 4 using namespace std;
 5 const int maxn = 150;
 6 int n,k;
 7 vector<int>G[10010];
 8 int link[maxn];
 9 bool vis[maxn];
10 
11 void add_edge(int u,int v)
12 {
13     G[u].push_back(v);
14 }
15 
16 bool dfs(int u)
17 {
18     for(int i=0;i<G[u].size();i++)
19     {
20         int v=G[u][i];
21         if(!vis[v])
22         {
23             vis[v]=true;
24             if(link[v]==-1||dfs(link[v]))
25             {
26                 link[v]=u;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 int main()
34 {
35    //freopen("a.txt","r",stdin);
36     int t,b,c;
37     scanf("%d",&t);
38     while(t--)
39     {
40         scanf("%d%d",&n,&k);
41         for(int i=0;i<n;i++) G[i].clear();
42         for(int i=0;i<k;i++)
43         {
44             scanf("%d%d",&b,&c);
45             add_edge(b-1,c-1);
46         }
47         int ans=0;
48         memset(link,-1,sizeof(link));
49         for(int i=0;i<n;i++)
50         {
51             memset(vis,0,sizeof(vis));
52             if(dfs(i)) ans++;
53         }
54         printf("%d
",n-ans);
55     }
56     return 0;
57 }