当前位置: 首页 > news >正文

详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)

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喜欢玩电脑游戏&#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡&#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵&#xff0c;使得这些士兵能了望到所有的路。 注意&…...

解决The Tomcat connector configured to listen on port 8080 failed to start

问题 启动javar报错&#xff0c;提示如下 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实战

文章目录 深度学习自然语言处理&#xff08;NLP&#xff09;模型BERT&#xff1a;从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络&#xff08;RNN&#xff09;与长短时记忆网络&#xff08;LSTM&#xff09;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语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是…...

C#用Array类的FindAll方法和List<T>类的Add方法按关键词在数组中检索元素并输出

目录 一、使用的方法 1. Array.FindAll(T[], Predicate) 方法 &#xff08;1&#xff09;定义 &#xff08;2&#xff09;示例 2.List类的常用方法 &#xff08;1&#xff09;List.Add(T) 方法 &#xff08;2&#xff09;List.RemoveAt(Int32) 方法 &#xff08;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官网&#xff1a;https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢&#xff0c;可以使用淘宝定制的 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步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;前面章节主要介绍了bresenham直线插值运动&#xff0c;本节内容介绍让两个电机完成连续的直线运动,目标是画一个正五角星 一、五角星图介绍 五角星总共10条直线&#xff0c;10个顶点。设定左下角为原点…...

Elasticsearch:基本 CRUD 操作 - Python

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

1992-2022年全国及31省对外开放度测算数据(含原始数据+计算结果)(无缺失)

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

JVM之GC垃圾回收

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

自然语言学习nlp 六

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

fpga 需要掌握哪些基础知识?

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

Qt未来市场洞察

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

GPT-4模型中的token和Tokenization概念介绍

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

宽字节注入漏洞原理以及修复方法

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

【Linux】SystemV IPC

进程间通信 一、SystemV 共享内存1. 共享内存原理2. 系统调用接口&#xff08;1&#xff09;创建共享内存&#xff08;2&#xff09;形成 key&#xff08;3&#xff09;测试接口&#xff08;4&#xff09;关联进程&#xff08;5&#xff09;取消关联&#xff08;6&#xff09;释…...

iview 页面中判断溢出才使用Tooltip组件

使用方法 <TextTooltip :content"contentValue"></TextTooltip> 给Tooltip再包装一下 <template><Tooltip transfer :content"content" :theme"theme" :disabled"!showTooltip" :max-width"300" :p…...

如何使用websocket

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

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...