题目描述
H 国有 n个城市，这 n 个城市用 n−1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。
H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
输入输出格式
输入格式：
第一行一个整数 n，表示城市个数。
接下来的 n−1 行，每行 3个整数，u,v,w每两个整数之间用一个空格隔开，表示从城市u到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。
接下来一行一个整数 m，表示军队个数。
接下来一行 m个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。
输出格式：
一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出−1。
输入输出样例
输入样例1：
|
1 2 3 4 5 6 7 |
4 1 2 1 1 3 2 3 4 3 2 2 2 |
输出样例1：
|
1 2 |
3 |
说明
【输入输出样例说明】
第一支军队在 2 号点设立检查点，第二支军队从 2 号点移动到 3 号点设立检查点，所需时间为 3 个小时。
【数据范围】
保证军队不会驻扎在首都。
对于 20%的数据，2≤n≤10；
对于 40%的数据，2 ≤n≤50,0<w <10^5
对于 60%的数据，2 ≤ n≤1000,0<w <10^6
对于 80%的数据，2 ≤ n≤10,000
对于 100%的数据，2≤m≤n≤50,000,0<w <10^9
NOIP 2012 提高组 第二天 第三题
题解
这道题确实蛮难想的，又是二分又是贪心，还要用倍增来实现
具体看代码吧，注释得挺详细的
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=100005; int Nt[MAXN],Head[MAXN],to[MAXN],w[MAXN],tot; int n,m; long long f[MAXN][18],dis[MAXN][18]; bool vis[MAXN],used[MAXN]; int army[MAXN],restbj[MAXN],restmin[MAXN]; struct node{long long rest;int id;}a[MAXN],b[MAXN]; int nb,na; void add(int a,int b,int c){ Nt[++tot]=Head[a]; to[tot]=b; w[tot]=c; Head[a]=tot; } void dfs(int x){ for(int i=Head[x];i;i=Nt[i]){ int y=to[i]; if(y==f[x][0]) continue; f[y][0]=x,dis[y][0]=w[i]; dfs(y); } } int checkok(int x,int las){//找还没被堵死的子树 int bj=1,i,bbj=0; if(vis[x])return 1;//遇到已经没气了的军队，返回1 for(i=Head[x];i;i=Nt[i]){ if(to[i]==las)continue;bbj=1; if(!checkok(to[i],x)){//如果继续走能访问到叶子节点 bj=0;//为了让根节点遍历完所有子树还能返回0 if(x==1) b[++nb].id=to[i],b[nb].rest=w[i];//并且是根节点，就记录下这棵子树（不能直接返回0，还要遍历完所有子树） else return 0;//如果不是根节点，直接返回0 } } if(!bbj)return 0;//到叶子节点，返回0 return bj; } bool cmp(node x,node y){return x.rest>y.rest;} bool solve(long long mid){ na=0,nb=0; int x,now; long long num=0; for(int i=1;i<=n;++i)vis[i]=restbj[i]=0;//初始化 for(int i=1;i<=m;i++)used[i]=0;//初始化 for(int i=1;i<=m;++i){//枚举灭一个军队 x=army[i],num=0; for(int j=17;j>=0;--j)//军队向上跳，要么跳到根节点下，要么跳不动不跳了 if(f[x][j]>1&&num+dis[x][j]<=mid) num+=dis[x][j],x=f[x][j]; if(f[x][0]==1&&num+dis[x][0]<=mid){//如果这支军队在根节点下并且还有口气 a[++na].rest=mid-num-dis[x][0],a[na].id=i;//记录下它们剩余体力和编号 if(!restbj[x]||a[na].rest<restmin[x]) restmin[x]=a[na].rest,restbj[x]=i;//更新它们所在节点的最小体力值和对应的队伍编号 } else vis[x]=1;//如果没气了，标记 } if(checkok(1,0))return 1;//都被堵死了，可行！ sort(a+1,a+1+na,cmp),sort(b+1,b+1+nb,cmp);//将剩余军队和还没有封死的子树降序排序 now=1;used[0]=1;//很重要 for(int i=1;i<=nb;++i){//枚举每一棵未封死的子树 if(!used[restbj[b[i].id]]){used[restbj[b[i].id]]=1;continue;}//如果子树上有队伍，子树标记为用过 while(now<=na&&(used[a[now].id]||a[now].rest<b[i].rest))++now;//now是指已用过的队伍 if(now>na)return 0; used[a[now].id]=1; } return 1; } int main(){ long long sum=0; cin>>n; for(int i=1;i<n;++i){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c);sum+=c; } cin>>m; for(int i=1;i<=m;++i){ scanf("%d",&army[i]); } dfs(1); for(int i=1;i<=17;i++){ for(int j=1;j<=n;j++){ f[j][i]=f[f[j][i-1]][i-1]; dis[j][i]=dis[j][i-1]+dis[f[j][i-1]][i-1]; } } long long l=0,r=sum+1; int ans=-1; while(l<=r){ long long mid=(l+r)>>1; if(solve(mid))r=mid-1,ans=mid; else l=mid+1; } cout<<ans; return 0; } |