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)


相关推荐

  • Excel VBA编程教程(基础一)

    Excel VBA编程教程(基础一)VBA介绍VisualBasicforApplications(VBA)是VisualBasic的一种宏语言,是微软开发出来在其桌面应用程序中执行通用的自动化(OLE)任务的编程语言。主要能用来扩展Windows的应用程序功能,特别是MicrosoftOffice软件。说简单点,VBA是运行在MicrosoftOffice软件之上,可以用来编写非软件自带的功能的编程语言。Office软件提供丰富的功能接口,VBA可以调用它们,实现自定义的需求。基本上,能用鼠标和键盘能做的

  • BatchMD5Modify_4F-MDMB-BUTINACA

    BatchMD5Modify_4F-MDMB-BUTINACA写前bb最早是看了matlab的代码,搭了环境,demo也跑了,就再也没碰过了。之后想自己把测试和训练部分全部跑通,找了个用pytorch写的代码,看的过程中发现自己还是很多细节部分不是很清楚。虽然文章写的很一笔带过,但是看着代码会发现还是很多疑问的。代码地址:gayhub代码的requirements:UbuntuPython2.7(useAnaconda2.*here)…

  • Laravel5.2中Eloquent与DB类的区别是什么?

    Laravel5.2中Eloquent与DB类的区别是什么?

  • DejaGnu

    DejaGnu

  • Ascii code_扩展ascii码表

    Ascii code_扩展ascii码表ASCII码表如下:Bin(二进制)Oct(八进制)Dec(十进制)Hex(十六进制)缩写/字符解释000000000000x00NUL(null)空字符000000010110x01SOH(startofheadline)标题开始000000100220x02STX(startoftext)正文开始0000001103…

  • DirectX Repair(DirectX修复工具)官方中文增强版V4.1.0.30770 | directx repair修复工具增强版下载[通俗易懂]

    DirectX Repair(DirectX修复工具)官方中文增强版V4.1.0.30770 | directx repair修复工具增强版下载[通俗易懂]directxrepair修复工具增强版是一款专业优秀效果确凿的系统级DirectX修复工具,专门针对并近乎完美的修复0xc000007b进不了系统以及0xc000007b蓝屏问题,采用傻瓜式一键设计,界面简洁大方,使用也非常简单,大家只需要点击主界面上的“检测并修复”按钮,directxrepair就会自动完成校验、当前系统DirectX状态检测、下载、修复以及注册的全部功能,若发现异常则会提醒大家进行修复,所以无需担心directxrepair怎么用的问题,威航软件园提供…

发表回复

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

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