CF1029E Tree with Small Distances (贪心)
2024-09-24 07:33:44
题目大意:给你一棵边权为1的树,让你加入一些边,使得根节点(1号节点)到其他节点的最短距离不大于2
并没有想到贪心......
正解的贪心思路是这样的
用一个堆维护当前距离最远的点,然后把根节点和它的父节点连起来
这样,父节点周围一圈的节点到根的距离都不大于2,把这些节点都从堆里删除
实际操作的时候,并不需要删除它们,只需要把它们标记一下,等它们弹出堆的时候,continue即可
不断按照这个思路贪心,直到所有节点到根的距离都不大于2即可
#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 200010
#define ll long long
using namespace std;
//re
int gint()
{
int ret=,fh=;char c=getchar();
while(c<''||c>''){if(c=='-')fh=-;c=getchar();}
while(c>=''&c<=''){ret=ret*+c-'';c=getchar();}
return ret*fh;
}
int n,m,K,ma,cte,num;
int head[N],vis[N],use[N],dis[N],fa[N];
struct Edge{int to,nxt,val;}edge[N*];
void ae(int u,int v){
cte++;edge[cte].to=v;
edge[cte].nxt=head[u],head[u]=cte;}
struct node{
int id,d;
friend bool operator<(const node &s1,const node &s2)
{return s1.d<s2.d;}
node(int id,int d):id(id),d(d){} node(){}
};
void bfs()
{
queue<int>q;q.push();
while(!q.empty())
{
int u=q.front();q.pop();
for(int j=head[u];j;j=edge[j].nxt){
int v=edge[j].to;
if(v==fa[u]) continue;
fa[v]=u,dis[v]=dis[u]+;
q.push(v);
}
}
}
int solve()
{
priority_queue<node>q;
for(int i=;i<=n;i++)
if(dis[i]>) q.push(node(i,dis[i]));
int ans=;
while(!q.empty())
{
node k=q.top();q.pop();
int x=k.id,y=fa[x];
if(vis[x]) continue; vis[x]=;
dis[y]=,vis[y]=,ans++;
for(int j=head[y];j;j=edge[j].nxt){
int v=edge[j].to;
dis[v]=min(dis[v],),vis[v]=;
q.push(node(v,dis[v]));
}
}return ans;
} int main()
{
scanf("%d",&n);
int x,y,z,fx;
for(int i=;i<n;i++)
x=gint(),y=gint(),ae(x,y),ae(y,x);
bfs();
printf("%d\n",solve());
return ;
}
最新文章
- 在 CSS 预编译器之后:PostCSS
- Linux系统性能分析
- json解析jackson ,Gson,等知识总结
- 安装及升级node
- 【log4net】配置文件
- Codeforces Round #316 (Div. 2) D、E
- ie6兼容性
- hdu 4277
- 【Js应用实例】限制上传图片大小
- HCatalog
- Unity 数据Json格式的转换
- C语言实现十六进制字符串转数字
- CF1114D 【Flood Fill】
- openssl 1.1.1 reference
- SQL批量更新数据
- mdf ldf添加到数据库
- mysql数据类型介绍(含text,longtext,mediumtext说明)
- 稳定获取Android设备唯一码(UUID)的解决方案
- Exclude the folders/files for indexing
- IOS安卓常见问题
热门文章
- URL回车后发生了什么
- CF859C Pie Rules 动态规划 逆推_思维题
- 基于selectors模块实现并发的FTP
- js 时间戳 中国标准时间 年月日 日期之间的转换
- easyUI combobox的使用
- WebAssembly学习(二):Windows10下WebAssembly C/C++编译环境的搭建与Hello World尝试
- ES6 学习6 数组的扩展
- IDEA Maven Web项目 clone到本地导入到Eclipse中,启动服务器的时候会出现这个错误:SEVERE: Exception starting filter [hiddenHttpMethodFilter]
- vue自定义一个过滤器
- 新建Eclipse工作空间,复制原有的配置(转)