noip2018提高组初赛解析_NOIP提高组

noip2018提高组初赛解析_NOIP提高组题目背景NOIP2012提高组DAY2试题。题目描述H国有n个城市,这n个城市用n-1条双向道路相互连通构成一棵树,1号城市是首都,也是树中的根节点。H国的首|都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

题目背景

NOIP2012 提高组 DAY2 试题。

题目描述

H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。

H 国的首|都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

输入格式

第一行一个整数 n,表示城市个数。
接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。
接下来一行一个整数 m,表示军队个数。
接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。

输出格式

共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

样例数据 1

输入

4

1 2 1

1 3 2

3 4 3

2

2 2

输出

3

备注

【样例说明】
第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间为 3 个小时。

【数据范围】
保证军队不会驻扎在首都。
对于 20%  的数据,2≤n≤10;
对于 40%  的数据,2≤n≤50,0<w<105;
对于 60%  的数据,2≤n≤1000,0<w<106;
对于 80%  的数据,2≤n≤10,000;
对于 100% 的数据,2≤m≤n≤50,000,0<w<109。

 

解析:

       挺有意思的一道题。

       然而到现在我都不知道暴力怎么打。。。

       以下解析借鉴于这位大佬:[NOIP2012提高组]疫情控制 

       首先,这道题是要求最少的时间,可以二分答案

       然后是一个贪心的思路:让每支军队尽在二分的时间内尽可能多的控制城市,所以尽量向上爬

       因为军队越往上,能封住的叶子节点就越多(至少不会减少),那我们在能往上的情况下,尽可能往上。

       一支军队如果不能到根节点,就让其在能爬到的最高点停下,并封锁这个节点。

       如果能则记录下它剩下的时间和它经过的<根节点的儿子>的编号(即它从哪个儿子过来的)。

       然后我们DFS出已经被封锁的节点,如果一个节点的所有儿子都被封锁,则该节点也算被封锁。

       之后我们把所有<没被封锁的,根节点的儿子>的编号和到根节点的距离记录下来。

       再然后,我们的任务就是把刚刚记录的那些节点,用剩下的能到达根节点的军队去覆盖。于是又是贪心,把节点按照到根节点的距离升序排序,把军队按照剩余时间升序排序,然后对于一个节点,用剩余时间最少的,且比这个节点到根节点的距离大(因为要走过去)的军队覆盖。(就是尽量用剩余时间少的军队去覆盖)

       注意:如果一个军队“经过的<根节点的儿子>”没有被覆盖,则优先覆盖。

       最后如果能成功覆盖所有根节点的儿子,则说明答案可行,否则不可行。

       对于让军队向上爬的过程,我们可以用倍增的方法进行优化,所以要先预处理。

 

       整理思路:

       ①预处理倍增。

       ②二分答案。

       对于每个二分的答案:

      ①让每个军队尽可能向上爬。对于不能到根节点的,让其在能到达的最高节点停下,否则记录下来。对记录数据排序。

      ②找出所有未被封锁的<根节点的儿子>记录。对记录数据排序。

      ③用剩余军队覆盖所有未被封锁的根节点的儿子。判断答案是否可行。

 

代码:
 

#include <bits/stdc++.h>
using namespace std;

const int Max=50005;
int n,m,size,l,r,mid,tot1,tot2;
int first[Max],num[Max],f[Max][18],d[Max][18],p[Max],vis[Max];
struct bian{int to,next,len;};
bian edge[Max<<1];
struct shu{int id,len;};
shu a[Max],b[Max];

inline int get_int()
{
	int x=0,f=1;
	char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	if(c=='-') f=-1,c=getchar();
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x*f;
}

inline void build(int x,int y,int z)
{
	edge[++size].next=first[x];
	first[x]=size;
	edge[size].to=y,edge[size].len=z;
}

inline void dfs(int point,int fa)
{
	for(int u=first[point];u;u=edge[u].next)
	{
	  int to=edge[u].to;
	  if(to==fa) continue;
	  f[to][0]=point,d[to][0]=edge[u].len;
	  dfs(to,point);
	}
}

inline void pre()
{
	for(int j=1;j<=16;j++)
	   for(int i=1;i<=n;i++)
	     if(f[i][j-1]) f[i][j]=f[f[i][j-1]][j-1],d[i][j]=d[i][j-1]+d[f[i][j-1]][j-1];
}

inline void search(int point,int fa)
{
	if(vis[point]) return;
	vis[point]=1;int tag=0;
	for(int u=first[point];u;u=edge[u].next)
	{
	  int to=edge[u].to;
	  if(to==fa) continue;
	  tag=1;
	  search(to,point);
	  vis[point]&=vis[to];
	}
	if(!tag) vis[point]=0;  //叶子节点需特判
}

inline bool comp(const shu &a,const shu &b){return a.len<b.len;}
inline bool check(int mid)
{
	tot1=tot2=0;
	for(int i=1;i<=n;i++) vis[i]=0;
	for(int i=1;i<=m;i++)
	{
	  int sum=0,x=p[i];
	  for(int k=16;k>=0;k--)
	  	if(f[x][k]>1&&sum+d[x][k]<=mid) sum+=d[x][k],x=f[x][k];
	  if(f[x][0]==1&&sum+d[x][0]<=mid) a[++tot1].len=mid-sum-d[x][0],a[tot1].id=x;
	  else vis[x]=1;
	}
	search(1,0);
	if(vis[1]) return 1;
	for(int u=first[1];u;u=edge[u].next)
	  if(!vis[edge[u].to]) b[++tot2].len=edge[u].len,b[tot2].id=edge[u].to;
	sort(a+1,a+tot1+1,comp),sort(b+1,b+tot2+1,comp);
	if(tot1<tot2) return 0;
    int tag=1;
    for(int i=1;i<=tot1;i++)
    {
      if(!vis[a[i].id]) vis[a[i].id]=1;   //题解中的优先覆盖
      else if(a[i].len>=b[tag].len) vis[b[tag].id]=1;
      while(tag<=tot2&&vis[b[tag].id]) tag++;
      if(tag>tot2) return 1;
    }
    return tag>tot2;
}

int main()
{
	n=get_int();
	for(int i=1;i<n;i++)
	{
	  int x=get_int(),y=get_int(),z=get_int();
	  build(x,y,z),build(y,x,z);
	}
	m=get_int();
	for(int i=1;i<=m;i++) p[i]=get_int();
	dfs(1,0);
	pre();
	l=0,r=1e9;int tag=0;
	while(l<r)
	{
	  mid=(l+r)>>1;
	  if(check(mid)) tag=1,r=mid;
	  else l=mid+1;
	}
	if(tag) cout<<r<<"\n";
	else cout<<"-1\n";
	return 0; 
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/172070.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Navicat15激活码一直生成不了(注册激活)

    (Navicat15激活码一直生成不了)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.htmlHQE565NV3W-eyJsaWNlbnNlSWQi…

  • nginx安装与fastdfs配置–阿里云

    nginx安装与fastdfs配置–阿里云

  • AB PLC 报错Compact I/O end cap missing

    AB PLC 报错Compact I/O end cap missing•(Type03)I/OFault•(Code00)CompactI/Oendcapmissing报错就是少了这个右终端挡板

    2022年10月24日
  • stm32H747_STM32H743的cache

    stm32H747_STM32H743的cache一、H.264的来源和特点H.264是国际标准化组织(ISO)和国际电信联盟(ITU)共同提出的继MPEG4之后的新一代数字视频压缩格式,它即保留了以往压缩技术的优点和精华又具有其它压缩技术无法比拟的许多优点。 1.低码流和MPEG2和MPEG4ASP等压缩技术相比,在同等图像质量下,采用H.264技术压缩后的数据量只有MPEG2的1/8,MPEG4的1/3。 2.高

  • struts2的拦截器(4):通过继承AbstractInterceptor抽象类定义自己的拦截器

    struts2的拦截器(4):通过继承AbstractInterceptor抽象类定义自己的拦截器抽象类AbstractInterceptor实现了Interceptor接口,提供了init和destroy方法的空实现。如果我们的拦截器不需要打开资源,则可以无需实现这两个方法。可见通过继承AbstractInterceptor抽象类来实现自定义拦截器会更简单。将上篇文章中的SimpleInterceptor.java改为如下实现,其余所有代码一律不变:publicclassSim

  • 不能管家的AI机器狗不是好宠物?「建议收藏」

    文/智能相对论(ID:aixdlun)作者/离离近日,波士顿动力的网红大黄狗Spot因为学会“做家务”而登上了微博热搜。继跨年夜的芭蕾小碎步之后,再次引起全网热议。这次的“进化”要归功于波士顿动力新推出的Spot系列三大新品──SpotEnterprise、SpotArm以及全新升级系统Scout。软件与硬件的同时更新让这只大黄狗get了跳绳、捡垃圾、挖土种花、收拾衣服、写字、拖重物、开关门等一系列新技能。有了人工智能的“加持”,机器狗似乎变得比真实的狗狗更加“聪明”,能做到

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号