首页 > 代码库 > HDU 1054 Strategic Game (树形dp)
HDU 1054 Strategic Game (树形dp)
题目链接
题意:
给一颗树，用最少的点覆盖整棵树。
分析:
1：以当前节点为根节点，在该节点排士兵守护道路的最小消耗。在这种情况下，他的子节点可以安排士兵，也可以不安排士兵。可以从各个子节点两个不同状态（存在士兵，不存在士兵）的最值中选出最小的消耗，然后相加就求出了当前节点派士兵的最小消耗。
2：以当前节点为根节点，不存在士兵。这种情况十分清楚，因为当前节点没有士兵，那么这个节点到子节点之间的道路没有人守护，那么子节点就必须要安排士兵，因此这种情况下。这个节点的最小消耗就是每个子节点存在士兵的情况下的最小消耗的和。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #include <vector> 8 #define LL __int64 9 const int maxn = 1500+10;10 using namespace std;11 int d[maxn], a[maxn], vis[maxn];12 vector<int>v[maxn];13 14 void dfs(int root)15 {16 int i;17 vis[root] = 1;18 int len = v[root].size();19 for(i = 0; i < len; i++)20 {21 int tmp = v[root][i];22 if(vis[tmp]) continue;23 dfs(tmp);24 d[root] += a[tmp];25 a[root] += min(a[tmp], d[tmp]);26 }27 a[root] ++;28 }29 int main()30 {31 int n, i, x, m, b;32 while(~scanf("%d", &n))33 {34 memset(a, 0, sizeof(a));35 memset(d, 0, sizeof(d));36 memset(vis, 0, sizeof(vis));37 38 for(i = 0; i < n; i++)39 v[i].clear();40 while(n--)41 {42 scanf("%d%*c%*c%d%*c", &x, &m);43 while(m--)44 {45 cin>>b;46 v[x].push_back(b);47 v[b].push_back(x);48 }49 }50 dfs(0);51 cout<<min(d[0], a[0])<<endl;52 }53 return 0;54 }
HDU 1054 Strategic Game (树形dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。