简答题
偏难
#23494
疫情控制 【问题描述】 H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。 H 国的首都爆发了一…
疫情控制
【问题描述】
H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
【输入】
输入文件名为 blockade.in。
第一行一个整数 n,表示城市个数。
接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。
接下来一行一个整数 m,表示军队个数。
接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。
【输出】
输出文件为 blockade.out。
共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
【输入输出样例】

【输入输出样例说明】
第一支军队在 2 号点设立检查点,第二支军队从 2 号点移动到 3 号点设立检查点,所需时间为 3 个小时。
【数据范围】
保证军队不会驻扎在首都。

答案与解析
正确答案:<p style="text-align: left;">#include <bits/stdc++.h></p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int Max=50005;</p><p style="text-align: left;">int n,m,size,l,r,mid,tot1,tot2;</p><p style="text-align: left;">int first[Max],num[Max],f[Max][18],d[Max][18],p[Max],vis[Max];</p><p style="text-align: left;">struct bian{int to,next,len;};</p><p style="text-align: left;">bian edge[Max<<1];</p><p style="text-align: left;">struct shu{int id,len;};</p><p style="text-align: left;">shu a[Max],b[Max];</p><p> </p><p style="text-align: left;">inline int get_int()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0,f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c=='-') f=-1,c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void build(int x,int y,int z)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge[++size].next=first[x];</p><p style="text-align: left;"><span style="white-space:pre"> </span>first[x]=size;</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge[size].to=y,edge[size].len=z;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void dfs(int point,int fa)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[point];u;u=edge[u].next)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int to=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(to==fa) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span> f[to][0]=point,d[to][0]=edge[u].len;</p><p style="text-align: left;"><span style="white-space:pre"> </span> dfs(to,point);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void pre()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int j=1;j<=16;j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=1;i<=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span> 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];</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void search(int point,int fa)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(vis[point]) return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[point]=1;int tag=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[point];u;u=edge[u].next)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int to=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(to==fa) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span> tag=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> search(to,point);</p><p style="text-align: left;"><span style="white-space:pre"> </span> vis[point]&=vis[to];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!tag) vis[point]=0; //叶子节点需特判</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline bool comp(const shu &a,const shu &b){return a.len<b.len;}</p><p style="text-align: left;">inline bool check(int mid)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>tot1=tot2=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=n;i++) vis[i]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=m;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int sum=0,x=p[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int k=16;k>=0;k--)</p><p style="text-align: left;"><span style="white-space:pre"> </span> <span style="white-space:pre"> </span>if(f[x][k]>1&&sum+d[x][k]<=mid) sum+=d[x][k],x=f[x][k];</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(f[x][0]==1&&sum+d[x][0]<=mid) a[++tot1].len=mid-sum-d[x][0],a[tot1].id=x;</p><p style="text-align: left;"><span style="white-space:pre"> </span> else vis[x]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>search(1,0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(vis[1]) return 1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[1];u;u=edge[u].next)</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(!vis[edge[u].to]) b[++tot2].len=edge[u].len,b[tot2].id=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(a+1,a+tot1+1,comp),sort(b+1,b+tot2+1,comp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(tot1<tot2) return 0;</p><p style="text-align: left;"> int tag=1;</p><p style="text-align: left;"> for(int i=1;i<=tot1;i++)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> if(!vis[a[i].id]) vis[a[i].id]=1; //题解中的优先覆盖</p><p style="text-align: left;"> else if(a[i].len>=b[tag].len) vis[b[tag].id]=1;</p><p style="text-align: left;"> while(tag<=tot2&&vis[b[tag].id]) tag++;</p><p style="text-align: left;"> if(tag>tot2) return 1;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> return tag>tot2;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> int x=get_int(),y=get_int(),z=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span> build(x,y,z),build(y,x,z);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>m=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i<=m;i++) p[i]=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs(1,0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre();</p><p style="text-align: left;"><span style="white-space:pre"> </span>l=0,r=1e9;int tag=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(l<r)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span> mid=(l+r)>>1;</p><p style="text-align: left;"><span style="white-space:pre"> </span> if(check(mid)) tag=1,r=mid;</p><p style="text-align: left;"><span style="white-space:pre"> </span> else l=mid+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(tag) cout<<r<<"\n";</p><p style="text-align: left;"><span style="white-space:pre"> </span>else cout<<"-1\n";</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0; </p><p style="text-align: left;">}</p>
这道题暂未补解析。