题目大意:给你一棵边权为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 ;
}

最新文章

  1. 在 CSS 预编译器之后:PostCSS
  2. Linux系统性能分析
  3. json解析jackson ,Gson,等知识总结
  4. 安装及升级node
  5. 【log4net】配置文件
  6. Codeforces Round #316 (Div. 2) D、E
  7. ie6兼容性
  8. hdu 4277
  9. 【Js应用实例】限制上传图片大小
  10. HCatalog
  11. Unity 数据Json格式的转换
  12. C语言实现十六进制字符串转数字
  13. CF1114D 【Flood Fill】
  14. openssl 1.1.1 reference
  15. SQL批量更新数据
  16. mdf ldf添加到数据库
  17. mysql数据类型介绍(含text,longtext,mediumtext说明)
  18. 稳定获取Android设备唯一码(UUID)的解决方案
  19. Exclude the folders/files for indexing
  20. IOS安卓常见问题

热门文章

  1. URL回车后发生了什么
  2. CF859C Pie Rules 动态规划 逆推_思维题
  3. 基于selectors模块实现并发的FTP
  4. js 时间戳 中国标准时间 年月日 日期之间的转换
  5. easyUI combobox的使用
  6. WebAssembly学习(二):Windows10下WebAssembly C/C++编译环境的搭建与Hello World尝试
  7. ES6 学习6 数组的扩展
  8. IDEA Maven Web项目 clone到本地导入到Eclipse中,启动服务器的时候会出现这个错误:SEVERE: Exception starting filter [hiddenHttpMethodFilter]
  9. vue自定义一个过滤器
  10. 新建Eclipse工作空间,复制原有的配置(转)