[luogu]P2279 [HNOI2003]消防局的设立[贪心]
2024-09-05 20:29:34
[HNOI2003]消防局的设立
题目描述
2020年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了n-1条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话,我们称基地A到基地B的距离为d。
由于火星上非常干燥,经常引发火灾,人类决定在火星上修建若干个消防局。消防局只能修建在基地里,每个消防局有能力扑灭与它距离不超过2的基地的火灾。
你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时,消防队有能力及时扑灭火灾。
输入输出格式
输入格式:
输入文件名为input.txt。
输入文件的第一行为n (n<=1000),表示火星上基地的数目。接下来的n-1行每行有一个正整数,其中文件第i行的正整数为a[i],表示从编号为i的基地到编号为a[i]的基地之间有一条道路,为了更加简洁的描述树状结构的基地群,有a[i]<i。
输出格式:
输出文件名为output.txt
输出文件仅有一个正整数,表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。
输入输出样例
输入样例1#:
6
1
2
3
4
5
输出样例1#:
2
由于最大消防距离为定值,于是我们可以考虑贪心,每次选择深度最深的一个,在其爷爷处设立一个消防站,并以其爷爷为中心进行dfs,将长度为二的点都打上标记,打上标记将不再处理。
代码(练一下STL):
//2017.11.6 //greedy #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; inline int read(); namespace lys{ ; struct egde{ int to; int next; }e[N*]; struct DEEP{ int node,deep; bool operator < (const DEEP &a) const{ return a.deep>deep; } }; priority_queue<DEEP> q; bool used[N]; int pre[N],fa[N]; int n,cnt; void add(int x,int y){ e[++cnt].to=y;e[cnt].next=pre[x];pre[x]=cnt; e[++cnt].to=x;e[cnt].next=pre[y];pre[y]=cnt; } void dfs(int node,int deep){ q.push((DEEP){node,deep}); int i,v; for(i=pre[node];i;i=e[i].next){ v=e[i].to; if(v==fa[node]) continue ; fa[v]=node; dfs(v,deep+); } } void dfs1(int node,int deep){ ) return ; int i,v; used[node]=true ; for(i=pre[node];i;i=e[i].next){ v=e[i].to; dfs1(v,deep+); } } int main(){ int u,i; n=read(); ;i<n;i++){ u=read(); add(u,i+); } dfs(,); cnt=; while(!q.empty()){ DEEP x=q.top();q.pop(); if(used[x.node]) continue ; ); ,); cnt++; } printf("%d\n",cnt); ; } } int main(){ lys::main(); ; } inline int read(){ ,ff=; char c=getchar(); '){ ; c=getchar(); } +c-',c=getchar(); return kk*ff; }
最新文章
- 【Python基础学习六】函数
- SQL 变量
- 自定义webkit搜索框样式
- 160913、ionic + 高德地图定位
- 忘记windows的登陆密码
- php实现文件上传的源码
- -ffunction-sections -Wl,--gc-sections
- 由阿里巴巴笔试题看java加载顺序
- spring中propertyplaceholderconfigurer简介
- 2015年10月16日HTML标签表单笔记
- git 备份和恢复
- Pascal&#39;s Triangle II —LeetCode
- Matcher Pattern 正则表达式 示例
- Global build settings
- NGUI 3.5教程(四)Atlas和Sprite(制作图片button)
- 原生javascript选项卡
- ajax初探--实现简单实时验证
- git的学习笔记
- 用jquery+Asp.Net实现省市二级联动
- Python + Appium 获取当前屏幕的截图方法的封装
热门文章
- 【ABAP系列】SAP ABAP smartforms设备类型CNSAPWIN不支持页格式ZXXX
- cocos2dx基础篇(20) 扩展动作CCGridAction
- 决解nginx代理的django项目的admin站点无法访问,和没样式的问题。
- 红帽学习笔记[RHCSA] 第九课[文件归档、硬盘、分区以及自动挂载、Swap、链接]
- 多线程18-QueueUserWorkItem
- 关于Logcat
- Quartz-第三篇 quartz-misfire 错失,补偿执行
- 19: vue项目使用整理
- PowerEdge T630服务器安装机器学习环境(Ubuntu18.04、Nvidia 1080Ti驱动、CUDA及CUDNN安装)
- 41. First Missing Positive (JAVA)