题目大意：一城堡的所有的道路形成一个n个节点的树，如果在一个节点上放上一个士兵，那么和这个节点相连的边就会被看守住，问把所有边看守住最少需要放多少士兵。 dproot[ i ] 表示以i为根的子树，在i上放置一个士兵，看守住整个子树需要多少士兵。
掌握了一个图论知识：图的最小点覆盖=二分图的最大匹配
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 |
#include <cstdio>#include <cstring>#include <vector>using
namespace std;const
int N=100000;int link[N],used[N];vector v[N];int Dfs(int
k){ for(int
i=0;i<v[k].size();i++){ int
a=v[k][i]; if(used[a]==0){ used[a]=1; if(link[a]==-1||Dfs(link[a])){link[a]=k;return
1;} } }return
0;}int
main(){ int
i,count,a,n,b,t,k; while(~scanf("%d",&n)){ k=n; memset(link,-1,sizeof(link)); for(i=0;i<n;i++)v[i].clear(); while(n--){ scanf("%d:(%d)",&a,&b); while(b--){ scanf("%d",&t); v[a].push_back(t); v[t].push_back(a); } }count=0; for(i=0;i<k;i++){ memset(used,0,sizeof(used)); if(Dfs(i))count++; } printf("%d\n",count/2); } return
0;} |
树形Dp的效率明显比二分图匹配简单，而且编程复杂度低……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 |
#include <cstring> #include <cstdio>#include <vector>#include <algorithm>using
namespace std;const
int N=1505;int tree[N],all[N];vector v[N];void
Dfs(int
root,int
father){ tree[root]=1; int
sum=0; for(int
i=0;i<v[root].size();i++){ int
son=v[root][i]; if(son!=father){ Dfs(son,root); tree[root]+=all[son]; //覆盖当前点 sum+=tree[son]; //覆盖当前点的儿子节点 } } all[root]=min(sum,tree[root]); //DP取最优方案 }int
main(){ int
i,count,a,n,b,t,k; while(~scanf("%d",&n)){ k=n; for(i=0;i<n;i++)v[i].clear(); while(n--){ scanf("%d:(%d)",&a,&b); while(b--){ scanf("%d",&t); v[a].push_back(t); v[t].push_back(a); } } Dfs(0,0); printf("%d\n",min(tree[0],all[0])); } return
0;} |
HDU 1054 Strategic Game,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3624094.html