大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
个人评价 又爱又恨~~（最先就差不多写对了，结果初始化挂了）~~
1 题面
2 分析题面
2.0 题目简述
有一棵n个节点的，根为1的带权树和m支军队。现在有m支军队已经在某些点上，移动一支军队到一个相邻的点所花时间等于该条边的边权。军队可同时移动。问至少多少时间才可以使从1开始都到不了任何一个叶子节点（无法满足条件输出-1，根节点不能停军队）。
[概要]
题目相当于在一棵树上，用给定的军队去把这棵树的所有子树全部占领。求最大移动距离的最小值。
2.1 考虑算法
2.1.1 二分
这道题是要求最大移动距离的最小值即最少的时间，考虑二分答案
2.1.2 贪心
让每支军队尽可能向根节点爬
因为军队越往上，能封住的叶子节点就越多。在能往上的情况下，尽可能往上。
一支军队如果不能到根节点，就让其在能走到的最高点停下，并封锁这个节点
再然后，用剩下的能到达根节点的军队去覆盖
然后对于一个节点，用剩余时间最少的，且比这个节点到根节点的距离大的军队覆盖
[注意]如果一个军队经过的根节点的儿子没有被覆盖，则优先覆盖
2.1.3 倍增预处理
对于让军队向上走的过程，我们可以用倍增的方法进行优化，所以要先预处理
时间复杂度： O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
2.2 画图理解
如果以上讲解没有听懂，可以借助下面这组数据更详细地了解：
10 5
2 1 3
2 3 4
1 4 7
5 1 9
6 1 2
4 7 9
7 8 8
9 8 8
1 10 2
2 8 5 4 2
假设我们当前二分到的时间限制为9，模拟上面的步骤进行一遍。
-
上移军队：只有处于节点8的军队上移到了节点7，其余节点由于都在根节点的子节点上，不动。
找出闲置军队与需要被驻扎的节点。显然，闲置军队为目前处于4、2、5节点上的4支军队，需要被驻扎的节点为10、2、5、6节点。
-
初步处理这些数据。由于5号节点上的军队无法到达根节点再返回，且该节点需要被驻扎，因此该军队驻扎在五号节点；同理，7号节点上的军队驻扎在七号节点。
找出目前的闲置军队和需要被驻扎的节点。剩余的闲置军队为目前处于4、2节点上的3支军队，需要被驻扎的节点为2、6、10号节点。
-
利用贪心策略进行最后的匹配。最后，4号节点上的军队驻扎到6号节点，2号节点上的两支军队分别驻扎到2、10号节点。该方案是可行的。
3 代码实现
3.1 输入
没什么好说的
for(int i=1; i<n; i++){
scanf("%d%d%d",&x,&y,&z);
//建边
}
//预处理
scanf("%d",&m);
for(int i=1; i<=m; i++){
scanf("%d",&army[i]);//输入军队
}
3.2 预处理
节点的深度越小，控制的节点（子树内的节点）越多。所以可以贪心地把军队尽量向上提。
据此，我们需要把每个点往上的距离预处理，用倍增优化。
void dfs(int x,int l, ll hg){
f[x][0]=l,dis[x][0]=hg;
for(int i=1; i<=t; i++){
f[x][i]=f[f[x][i-1]][i-1];
dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1];
}//递推
for(int i=hd[x]; i!=-1; i=nxt[i]){
//遍历x的出边
if(to[i]!=l){
dfs(to[i],x,e[i]);
}
}
}//树上倍增预处理
3.3 二分答案
根据前面的分析，我们在 check的时候要尽量把军队往上走
当二分答案后，设答案为 k，这里会有两种情况
3.3.1 可以到达
他最高的位置一定是最优的，让他待在那里
3.3.2 无法到达
那求出他到达后还可以走多少时间 以及到达 1 1 1 前的儿子 i d id id，以便接下来的处理
3.3.3 根的叶子没有被控制完
把军队调到根节点的某个儿子，因此需要处理出有多少个儿子需要被控制，记录它们和根节点的距离
处理可以到达 1 的军队的去向
绿色节点可以跳到根节点然后到红色节点，于是就可以控制红色节点为根的子树
- 先将这些军队按照id深度从小到大排序。如果某一个军队的 i d id id 需要被控制，那么就让他不要到达根节点而直接待在 $ id $ 就行了。因为如果他不回去，肯定需要别的军队过来控制这个 i d id id，这样显然花费时间更大。
- 再将这些军队按照剩余时间从大到小排序，把需要被控制的点按倒根节点的距离从大到小排序。把这两个序列从前往后一一对比就行了！
3.3.4 是否合法的判断
如果 3.3.3 3.3.3 3.3.3中军队用完了可还有节点需要被控制，那么不合法；否则合法
3.3.5 All in all
对于每个二分的答案(即check中)：
①让每个军队尽可能向上爬。对于不能到根节点的，让其在能到达的最高节点停下，否则记录下来。对记录数据排序。
②找出所有未被封锁的根节点的儿子记录。对记录数据排序。
③用剩余军队覆盖所有未被封锁的根节点的儿子。判断答案是否可行。
int check(ll k){
//k表示当前的时限，即check函数传入的参数
int x,now;
ll s;
na=nb=0;//初始化
for(int i=1; i<=m; i++){
//全军上提
x=army[i],s=0;
for(int j=t; j>=0; j--){
if(f[x][j]>1 && s+dis[x][j]<=k){
s+=dis[x][j];
x=f[x][j];
}
}
//如果父亲是根而且距离够用
a[++na].w=k-s-dis[x][0];//记录是哪支军队
if(!rb[x]||a[na].w<mn[x])
//更新最小距离以进行下一次比较
//记录离这棵子树距离最小的军队
}
else //这个节点视为已被军队占领
}
//如果全被封锁了直接返回
//按剩余距离从大到小排序
now=xy[0]=1;
for(int i=1; i<=nb; i++){
//如果离这棵子树距离最小的军队没被占用
//视为它已被占用，继续
continue;
while(now<=na&&(xy[a[now].id]||a[now].w<b[i].w))++now;
//否则使用剩余距离最大的军队来覆盖它
//前提是还有剩余的军队而且此军队没被使用，距离足够
//如果军队不够则失败
//把本次用于覆盖的军队设为已用过
}
return 1;
}
3.4 输出
直接输出二分答案跑出来的答案即可
printf("%lld",ans);
3.5 总体代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=60002;
int n,m,cnt,na,nb,t;
int hd[N],nxt[N<<1],to[N<<1],f[N][21],army[N];
ll e[N<<1],dis[N][21],mn[N];
int vis[N],xy[N],rb[N];
struct node{
ll w;
int id;
}a[N],b[N];
void add(int u, int v, int w){
nxt[++cnt]=hd[u];
hd[u]=cnt;
to[cnt]=v;
e[cnt]=w;
}
void dfs(int x,int l, ll hg){
f[x][0]=l,dis[x][0]=hg;
for(int i=1; i<=t; i++){
f[x][i]=f[f[x][i-1]][i-1];
dis[x][i]=dis[x][i-1]+dis[f[x][i-1]][i-1];
}//递推
for(int i=hd[x]; i!=-1; i=nxt[i]){
//遍历x的出边
if(to[i]!=l){
dfs(to[i],x,e[i]);
}
}
}//树上倍增预处理
int df(int u,int l){
int fg=1,flag=0;
if(vis[u])return 1;
for(int i=hd[u];i!=-1;i=nxt[i]){
if(to[i]==l)continue;//如果是父亲就继续
flag=1;
if(!df(to[i],u)){
fg=0;
if(u==1) {
b[++nb].id=to[i];
b[nb].w=e[i];
}
else return 0;
}
}
if(!flag)return 0;
return fg;
}
bool cmp(node x,node y){
return x.w>y.w;
}
int check(ll k){
//k：当前时限
int x,now;
ll s;
na=nb=0;
memset(vis,0,sizeof(vis));
memset(rb,0,sizeof(rb));
memset(xy,0,sizeof(xy));
//初始化
for(int i=1; i<=m; i++){
//全军上提
x=army[i],s=0;
for(int j=t; j>=0; j--){
if(f[x][j]>1 && s+dis[x][j]<=k){
s+=dis[x][j];
x=f[x][j];
}
}
if(f[x][0]==1 && s+dis[x][0]<=k){
//父亲是根而且距离够用
a[++na].w=k-s-dis[x][0];//另外记录
a[na].id=i;//记录
if(!rb[x]||a[na].w<mn[x])
mn[x]=a[na].w,rb[x]=i;//更新最小距离以进行下一次比较
}
else vis[x]=1;
}
if(df(1,0))return 1;//已被驻守，返回true
sort(a+1,a+1+na,cmp);
sort(b+1,b+1+nb,cmp);
now=1;
xy[0]=1;
for(int i=1; i<=nb; i++){
if(!xy[rb[b[i].id]]){
xy[rb[b[i].id]]=1;
continue;
}
while(now<=na&&(xy[a[now].id]||a[now].w<b[i].w))++now;
if(now>na){
return 0;
}
xy[a[now].id]=1;
}
return 1;
}
int main(){
int x,y,z;
ll l=0,r=500000,mid,ans=-1;
scanf("%d",&n);//输入
t=(int)(log(n)/log(2))+1;//f数组和dist数组第二维下标的最大值
memset(hd,-1,sizeof(hd));//初始化
for(int i=1; i<n; i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);//双向建边
}
dfs(1,0,0);//初始化
scanf("%d",&m);//输入
for(int i=1; i<=m; i++){
scanf("%d",&army[i]);//输入军队
}
while(l<=r){
//二分答案
mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;//记录答案
}else {
l=mid+1;
}
}
printf("%lld",ans);//输出答案
return 0;
}
4 总结
-
完成这个题后，得到的教训是数组初始化和for循环结束条件一定要统一
-
相似题目：「NOIP2012」开车旅行 和 「NOIP2013」货车运输
完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。
发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/172061.html原文链接：https://javaforall.cn
【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛
【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...
