题目大意

N个节点构成一棵树形结构,在其中若干个节点上放置士兵,与被放置士兵的节点相连的边会被士兵看守。问需要至少在多少个节点上放置士兵,才能使得N-1条边都被看守。

题目分析

题目描述的结构为树形,且最优化问题,可以考虑使用树形动态规划来解决。将结构按照树根在上,树叶在下的结构进行排列,为了保证无后效性,需要对i节点上有无士兵的情况单独处理,设置状态 dp[i][0] 表示在节点i不放置士兵的情况下,节点i以下的边都被看守所需要放置士兵的最少数目;dp[i][1]表示在节点i放置士兵的情况下,节点i以下的所有边都被看守所需要放置士兵的最少数目。显然有递推关系: 
dp[i][0] = sum{dp[son_of_i][1]} 
dp[i][1] = sum{min{dp[son_of_i][0], dp[son_of_i][1]}}

实现(c++)

#include<stdio.h>
#include<vector>
#include<string.h>
#define min(a, b) a < b? a:b
using namespace std;
vector<int> gGraph[1505];
//使用 vector<int> gGraph[1505], 而不使用 vector<vector<int> >
//是因为题目多组数据,若使用 vector<vector<int> >,则在每组数据都会进行对 外层vecotr的 resize操作,减低效率
int dp[1505][2];
void Travel(int node){
if (gGraph[node].empty()){
dp[node][0] = 0; //node节点不放置士兵的情况下,node节点以下的所有边都被看守所需要的士兵总数
dp[node][1] = 1; //node节点放置士兵的情况下,node节点以下的所有边都被看守所需要的士兵总数
return;
}
dp[node][1] = 1;
for (int i = 0; i < gGraph[node].size(); i++){
Travel(gGraph[node][i]); //由叶子到根进行递推,后序遍历 //node节点不放置士兵的情况下,需要node节点的子节点都放置士兵
dp[node][0] += dp[gGraph[node][i]][1]; //node节点放置士兵,则其子节点可放可不放,选取最小值即可
dp[node][1] += min(dp[gGraph[node][i]][1], dp[gGraph[node][i]][0]); }
} int main(){
int n, root;
while (scanf("%d", &n) != EOF){ for (int i = 0; i < n; i++){
gGraph[i].clear();
} int node, num_adjacent, node_adjacent;
root = -1;
memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++){
scanf("%d:(%d)", &node, &num_adjacent);
if (root < 0)
root = node;
for (int j = 0; j < num_adjacent; j++){
scanf("%d", &node_adjacent);
gGraph[node].push_back(node_adjacent);
}
} Travel(root); int result = min(dp[root][0], dp[root][1]);
printf("%d\n", result);
}
return 0;
}

最新文章

  1. Yii2 modal中 ajax提交表单
  2. ssh
  3. C# 根据正则表达式来判断输入的是不是数字
  4. Jenkins实现生产环境部署文件的回滚操作(Windows)
  5. CSS等高布局
  6. Ant 执行 YUICompressor
  7. SSH_框架整合5--验证用户名是否可用
  8. Java中的大数处理类BigInteger和BigDecimar浅析
  9. c语言与c++基础知识
  10. bootstrap-treeview
  11. 自己动手,丰衣足食!一大波各式各样的ImageView来袭!
  12. 关于bootstrap 在MVC里 模态框里加载iframe页面做编辑的时候
  13. (iOS)关于@property和@synthesize的理解(原创)
  14. leetcode题解-122买卖股票的最佳时期
  15. Failed to mount component: template or render function not defined.
  16. 个人作业——final
  17. java-代码生成器
  18. CA证书扫盲,https讲解
  19. 如何读取抓取的wifi包内容
  20. 20169205 2016-2017-2 实验二nmap的使用与分析

热门文章

  1. USES_CONVERSION的使用和注意
  2. 百度MIP(百度版的google AMP)了解一下?
  3. Genral log(普通日志)与 Slow log(慢速日式)
  4. 编写每天定时切割Nginx日志的脚本
  5. atitit.自动生成数据库结构脚本,或者更换数据库,基于hibernate4
  6. 【LeetCode】Permutations II 解题报告
  7. HotSpot模板解释器目标代码生成过程源码分析
  8. 【LeetCode】065-验证数字
  9. lo4j 日志级别
  10. HADOOP 2.6 INSTALLING ON UBUNTU 14.04 (hadoop 2.6 部署到ubuntu 14.04上面)