湖南做网站 磐石网络引领/长春关键词优化公司
Description
Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。
他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。
注意,某个士兵在一个结点上时,与该结点相连的所有边将都可以被了望到。
请你编一程序,给定一树,帮Bob计算出他需要放置最少的士兵.
Format
Input
第一行 N,表示树中结点的数目。
第二行至第N+1行,每行描述每个结点信息,依次为:该结点标号i,k(后面有k条边与结点I相连)。
接下来k个数,分别是每条边的另一个结点标号r1,r2,…,rk。
对于一个n(0<n<=1500)个结点的树,结点标号在0到n-1之间,在输入数据中每条边只出现一次。
Output
输出文件仅包含一个数,为所求的最少的士兵数目。
Samples
输入数据 1
4
0 1 1
1 2 2 3
2 0
3 0
Copy
输出数据 1
1
Copy
Hint 答案为1(只要一个士兵在结点1上)。
思路1:树形DP
可以先看看详解洛谷P1352 没有上司的舞会(树形DP经典例题)-CSDN博客
定义状态dp[x][0/1]表示x这个节点不放/放士兵
根据题意,如果当前节点不放置士兵,那么它的子节点必须全部放置士兵,因为要满足士兵可以看到所有的边
dp[x][0] += dp[son][1]
其中son是u的子节点
如果当前节点放置士兵,只要将dp[x][1]加上它的子节点选不选的最小值就行了(因为树形dp自下而上,上面的节点不需要考虑)
dp[x][1]+=min(dp[son][0],dp[son][1])
代码(树形DP)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,u,v,dp[10001][2];
vector<int> vec[100001];
void dfs(int fa,int x)
{dp[x][1] = 1;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa){dfs(x,vec[x][i]);dp[x][0] += dp[vec[x][i]][1];dp[x][1] += min(dp[vec[x][i]][0],dp[vec[x][i]][1]);}
}
signed main()
{cin>>n;for(int i = 1;i <= n;i++){int p;cin>>p>>u;for(int j = 1;j <= u;j++){cin>>v;vec[p].push_back(v);vec[v].push_back(p);}}dfs(-1,0);cout<<min(dp[0][1],dp[0][0]);return 0;
}
思路2:贪心
可以按照反方向的深度优先遍历序列来进行贪心。每检查一个结点,如果当前点和当前点的父节点都不属于顶点覆盖集合,则将父节点加入到顶点覆盖集合,并标记当前节点和其父节点都被覆盖.
虽然说着思路很简单,但是代码细节蛮多的,可以参考一下。
代码(贪心)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,u,v,ans,fat[100001],cnt;
struct st
{int zhi,id;
}dp[100001];
bool vis[100001];
vector<int> vec[100001];
void dfs(int fa,int x,int dep)
{dp[++cnt] = {dep,x};fat[x] = fa;for(int i = 0;i < vec[x].size();i++)if(vec[x][i] != fa)dfs(x,vec[x][i],dep + 1);
}
bool cmp(st x,st y)
{return x.zhi > y.zhi;
}
signed main()
{cin>>n;for(int i = 1;i <= n;i++){int p;cin>>p>>u;for(int j = 1;j <= u;j++){cin>>v;vec[p].push_back(v);vec[v].push_back(p);}}vis[1501] = 1;dfs(1501,0,1);sort(dp + 1,1 + dp + n,cmp);for(int i = 1;i <= n;i++)if(vis[dp[i].id] == 0 && vis[fat[dp[i].id]] == 0){vis[fat[dp[i].id]] = 1;vis[dp[i].id] = 1;ans++;}cout<<ans;return 0;
}
结语
如果这篇博客对您有帮助的话,请点赞收藏关注支持一下呗!(o゜▽゜)o☆
相关文章:

详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)
Description Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。 注意&…...

解决The Tomcat connector configured to listen on port 8080 failed to start
问题 启动javar报错,提示如下 Description: The Tomcat connector configured to listen on port 8080 failed to start. The port may already be in use or the connector may be misconfigured. Action: Verify the connector’s configuration, identify a…...

深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战
文章目录 深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络(RNN)与长短时记忆网络(LSTM)Transform…...

C语言的循环结构
目录 前言 1.三种循环语句 1.while循环 2.for循环 2.1缺少表达式的情况 3.do while循环 2.break语句和continue语句 2.1在while循环中 2.2在for循环中 2.3在do while 循环中 3.循环的嵌套 4.go to语句 前言 C语⾔是结构化的程序设计语⾔,这⾥的结构指的是…...

C#用Array类的FindAll方法和List<T>类的Add方法按关键词在数组中检索元素并输出
目录 一、使用的方法 1. Array.FindAll(T[], Predicate) 方法 (1)定义 (2)示例 2.List类的常用方法 (1)List.Add(T) 方法 (2)List.RemoveAt(Int32) 方法 (3&…...

【前后端接口AES+RSA混合加解密详解(vue+SpringBoot)附完整源码】
前后端接口AES+RSA混合加解密详解(vue+SpringBoot) 前后端接口AES+RSA混合加解密一、AES加密原理和为什么不使用AES加密二、RSA加密原理和为什么不使用rsa加密三、AES和RSA混合加密的原理四、代码样例前端1. 请求增加加密标识2. 前端加密工具类3.前端axios请求统一封装,和返…...

React环境配置
1.安装Node.js Node.js官网:https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢,可以使用淘宝定制的 cnpm (gzip 压缩支持) 命令行工具代替默认的 npm。 ①使用 winR 输入 cmd 打开终端 ②依…...

Pandas 数据处理-排序与排名的深度探索【第69篇—python:文本数据处理】
文章目录 Pandas 数据处理-排序与排名的深度探索1. sort_index方法2. sort_values方法3. rank方法4. 多列排序5. 排名方法的参数详解6. 处理重复值7. 对索引进行排名8. 多级索引排序与排名9. 更高级的排序自定义10. 性能优化技巧10.1 使用nsmallest和nlargest10.2 使用sort_val…...

第8节、双电机多段直线运动【51单片机+L298N步进电机系列教程】
↑↑↑点击上方【目录】,查看本系列全部文章 摘要:前面章节主要介绍了bresenham直线插值运动,本节内容介绍让两个电机完成连续的直线运动,目标是画一个正五角星 一、五角星图介绍 五角星总共10条直线,10个顶点。设定左下角为原点…...

Elasticsearch:基本 CRUD 操作 - Python
在我之前的文章 “Elasticsearch:关于在 Python 中使用 Elasticsearch 你需要知道的一切 - 8.x”,我详细讲述了如何建立 Elasticsearch 的客户端连接。我们也详述了如何对数据的写入及一些基本操作。在今天的文章中,我们针对数据的 CRUD (cre…...

1992-2022年全国及31省对外开放度测算数据(含原始数据+计算结果)(无缺失)
1992-2022年全国及31省对外开放度测算数据(含原始数据计算结果)(无缺失) 1、时间:1992-2022年 2、来源:各省年鉴、国家统计局、统计公报、 3、指标:进出口总额(万美元)…...

JVM之GC垃圾回收
GC垃圾回收 如何判断对象可以回收 引用计数法 如果有对象引用计数加一,没有对象引用,计数减一,如果计数为零,则回收 但是如果存在循环引用,即A对象引用B对象,B对象引用A对象,会造成内存泄漏 可…...

自然语言学习nlp 六
https://www.bilibili.com/video/BV1UG411p7zv?p118 Delta Tuning,尤其是在自然语言处理(NLP)和机器学习领域中,通常指的是对预训练模型进行微调的一种策略。这种策略不是直接更新整个预训练模型的权重,而是仅针对模型…...

fpga 需要掌握哪些基础知识?
个人根据自己的一些心得总结一下fpga 需要掌握的基础知识,希望对你有帮助。 1、数电(必须掌握的基础),然后进阶学模电, 2、掌握HDL(verilog或VHDL)一般建议先学verilog,然后可以学…...

Qt未来市场洞察
跨平台开发:Qt作为一种跨平台的开发框架,具有良好的适应性和灵活性,未来将继续受到广泛应用。随着多设备和多平台应用的增加,Qt的前景在跨平台开发领域将更加广阔。 物联网应用:由于Qt对嵌入式系统和物联网应用的良好支…...

GPT-4模型中的token和Tokenization概念介绍
Token从字面意思上看是游戏代币,用在深度学习中的自然语言处理领域中时,代表着输入文字序列的“代币化”。那么海量语料中的文字序列,就可以转化为海量的代币,用来训练我们的模型。这样我们就能够理解“用于GPT-4训练的token数量大…...

宽字节注入漏洞原理以及修复方法
漏洞名称:宽字节注入 漏洞描述: 宽字节注入是相对于单字节注入而言的,该注入跟HTML页面编码无关,宽字节注入常见于mysql中,GB2312、GBK、GB18030、BIG5、Shift_JIS等这些都是常说的宽字节,实际上只有两字节。宽字节带来的安全问…...

【Linux】SystemV IPC
进程间通信 一、SystemV 共享内存1. 共享内存原理2. 系统调用接口(1)创建共享内存(2)形成 key(3)测试接口(4)关联进程(5)取消关联(6)释…...

iview 页面中判断溢出才使用Tooltip组件
使用方法 <TextTooltip :content"contentValue"></TextTooltip> 给Tooltip再包装一下 <template><Tooltip transfer :content"content" :theme"theme" :disabled"!showTooltip" :max-width"300" :p…...

如何使用websocket
如何使用websocket 之前看到过一个面试题:吃饭点餐的小程序里,同一桌的用户点餐菜单如何做到的实时同步? 答案就是:使用websocket使数据变动时服务端实时推送消息给其他用户。 最近在我们自己的项目中我也遇到了类似问题…...

C++ 调用lua 脚本
需求: 使用Qt/C 调用 lua 脚本 扩展原有功能。 步骤: 1,工程中引入 头文件,库文件。lua二进制下载地址(Lua Binaries) 2, 调用脚本内函数。 这里调用lua 脚本中的process函数,并…...

Centos 内存和硬盘占用情况以及top作用
目录 只查看内存使用情况: 内存使用排序取前5个: 硬盘占用情况 定位占用空间最大目录 top查看cpu及内存使用信息 前言-与正文无关 生活远不止眼前的苦劳与奔波,它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中&…...

【数据结构】堆(创建,调整,插入,删除,运用)
目录 堆的概念: 堆的性质: 堆的存储方式: 堆的创建 : 堆的调整: 向下调整: 向上调整: 堆的创建: 建堆的时间复杂度: 向下调整: 向上调整ÿ…...

v-if 和v-for的联合规则及示例
第073个 查看专栏目录: VUE ------ element UI 专栏目标 在vue和element UI联合技术栈的操控下,本专栏提供行之有效的源代码示例和信息点介绍,做到灵活运用。 提供vue2的一些基本操作:安装、引用,模板使用,computed&a…...

各互联网企业测绘资质调研
公司子公司产品产品介绍资质获得资质时间阿里巴巴高德高德地图作为阿里的全资子公司,中国领先的数字地图内容、导航和位置服务解决方案提供商,互联网地图行业龙头,2021年4月高德实现全月平均日活跃用户数超过1亿的重要里程碑,稳居…...

C++自定义函数详解
个人主页:PingdiGuo_guo 收录专栏:C干货专栏 铁汁们新年好呀,今天我们来了解自定义函数。 文章目录 1.数学中的函数 2.什么是自定义函数 3.自定义函数如何使用? 4.值传递和引用传递(形参和实参区分) …...

flask+vue+python跨区通勤人员健康体检预约管理系统
跨区通勤人员健康管理系统设计的目的是为用户提供体检项目等功能。 与其它应用程序相比,跨区通勤人员健康的设计主要面向于跨区通勤人员,旨在为管理员和用户提供一个跨区通勤人员健康管理系统。用户可以通过系统及时查看体检预约等。 跨区通勤人员健康管…...

Spring Boot动态加载Jar包与动态配置技术探究
Spring Boot动态加载Jar包与动态配置技术探究 1. 引言 在当今快节奏的软件开发领域,高效的开发框架是保持竞争力的关键。Spring Boot作为一款快速开发框架,以其简化配置、内嵌Web服务器、强大的开发工具等特性,成为众多开发者的首选。其背后…...

Lua metatable metamethod
示例代码 《programming in lua》里有一个案例很详细,就是写一个集合类的table,其负责筛选出table中不重复的元素并组合成一个新的table。本人按照自己的方式默写了一次,结果发现大差不差,代码如下: Set {} --集合--…...

HCIA-HarmonyOS设备开发认证V2.0-3.2.轻量系统内核基础-任务管理
目录 一、任务管理1.1、任务状态1.2、任务基本概念1.3、任务管理使用说明1.4、任务开发流程1.5、任务管理接口 一、任务管理 从系统角度看,任务是竞争系统资源的最小运行单元。任务可以使用或等待CPU、使用内存空间等系统资源,并独立于其它任务运行。 O…...