首页 > 代码库 > 【二分答案+lca】疫情控制
【二分答案+lca】疫情控制
版权声明:本篇随笔版权归作者Etta(http://www.cnblogs.com/Etta/)所有,转载请保留原地址!
Description
H 国有 n 个城市,这 n 个城市用 n-1 条双向道路相互连通构成一棵树,1 号城市是首都,也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。
现在,在 H国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等
于道路的长度(单位:小时)。
请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。
Input
第一行一个整数 n,表示城市个数。
接下来的 n-1 行,每行 3 个整数,u、v、w,每两个整数之间用一个空格隔开,表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树,且根节点编号为 1。
接下来一行一个整数 m,表示军队个数。
接下来一行 m 个整数,每两个整数之间用一个空格隔开,分别表示这 m 个军队所驻扎的城市的编号。
Output
共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。
Sample Input
4 1 2 1 1 3 2 3 4 3 2 2 2
Sample Output
3
Solution
调了将近一天……
总体思路:首先在连边之后dfs()倍增求出祖先f[x][i]和点x到第2^i个祖先的距离g[x][i]。接着二分答案,对于每一个时间t,将每一支军队在t内用倍增尽量往上提,一部分点可以在t内到达根节点1,则记下这些点,这些点经过的点1的儿子节点,以及到达点1后的剩余时间,并按时间升序排序。倍增之后找出未被到达的点1的儿子节点,并将他们按与点1的连边的长度升序排序,使用贪心,让之前已到达点1的军队占领这些儿子节点。
关键点:军队所在节点深度越小,控制的叶子节点到根节点的道路越多。因此贪心使用的是根节点的儿子节点。
易错点:dfs判断每一个儿子节点是否被占领时,要考虑到没有子节点的情况。贪心中过程中,每一个到达根节点的军队节点,如果他们所经过的儿子节点并没有被占领,则他们可以直接占领儿子节点。
小小的优化:第一遍dfs同时记下每个点到达根节点经过的儿子节点fr[x]。
关于时间复杂度:右区间最开始r=1e14 codevsAC然而洛谷TLE最后一个点,于是很不爽地改啊改,最终把r设为边的累加和终于AC,洛谷700ms+而codevs300ms+简直飞快……
Code
1 #include<cstdio> 2 #include<climits> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 const int A=5e4+10,C=16; 8 int n,m,s,ez,k,p=C-1,x,y,z,AR,tmp; 9 struct edge{ 10 int t,n,l; 11 }e[A*2]; 12 struct sn{ 13 int o,d; 14 }son[A]; 15 struct arrive{ 16 int fr; 17 long long lf; 18 }c[A]; 19 int h[A],fa[A],dp[A],f[A][C],fr[A],con[A],a[A]; 20 long long l,r,mid,t,maxn; 21 long long g[A][C]; 22 char ch; 23 24 void read(int &x) 25 { 26 x=0; 27 ch=getchar(); 28 while(ch<‘0‘||ch>‘9‘)ch=getchar(); 29 while(ch>=‘0‘&&ch<=‘9‘) 30 { 31 x=x*10+ch-‘0‘;ch=getchar(); 32 } 33 } 34 35 void build(int f,int t,int l) 36 { 37 e[++s].t=t; 38 e[s].n=h[f]; 39 h[f]=s; 40 e[s].l=l; 41 } 42 43 void dfs(int x,int dis,int from) 44 { 45 f[x][0]=fa[x]; 46 g[x][0]=dis; 47 fr[x]=from; 48 for(int i=1;i<=p;++i) 49 { 50 f[x][i]=f[f[x][i-1]][i-1]; 51 g[x][i]=g[x][i-1]+g[f[x][i-1]][i-1]; 52 } 53 for(int i=h[x];i;i=e[i].n) 54 { 55 k=e[i].t; 56 if(k!=fa[x]) 57 { 58 dp[k]=dp[x]+1; 59 fa[k]=x; 60 dfs(k,e[i].l,from); 61 } 62 } 63 } 64 65 void bz(int k,int x,long long time) 66 { 67 if(g[x][p]&&g[x][p]<=time) 68 { 69 c[++AR].lf=time-g[x][p]; 70 c[AR].fr=fr[x]; 71 return; 72 } 73 t=0; 74 for(int i=p;i>=0;--i) 75 if(dp[f[x][i]]>=1&&t+g[x][i]<=time) 76 { 77 t+=g[x][i];x=f[x][i]; 78 } 79 80 if(fa[x]!=1||t+g[x][0]>time)con[x]=1; 81 if(fa[x]==1&&t+g[x][0]<=time) 82 { 83 t+=g[x][0]; 84 c[++AR].lf=time-t; 85 c[AR].fr=x;//已到达 86 } 87 } 88 89 bool ddfs(int x) 90 { 91 bool he=0;//考虑到没有子树的情况 92 for(int i=h[x];i;i=e[i].n) 93 { 94 tmp=e[i].t;//全局变量的调用要小心 95 if(tmp!=fa[x]) 96 { 97 he=1; 98 if(!con[tmp]&&!ddfs(tmp)) 99 return false; 100 } 101 } 102 if(!he)return false; 103 return true; 104 } 105 106 bool cmp(sn x,sn y){return x.d<y.d;} 107 bool cmp2(arrive x,arrive y){return x.lf<y.lf;} 108 109 bool tf(long long time) 110 { 111 memset(con,0,sizeof(con)); 112 AR=0; 113 for(int i=1;i<=m;++i) 114 bz(i,a[i],time); 115 t=0; 116 for(int i=h[1];i;i=e[i].n) 117 { 118 k=e[i].t; 119 if(!con[k]&&!ddfs(k)) 120 { 121 son[++t].o=k; 122 son[t].d=e[i].l; 123 } 124 else con[k]=1;//避免重复使用c 125 } 126 if(!t)return true; 127 sort(son+1,son+t+1,cmp); 128 sort(c+1,c+AR+1,cmp2); 129 int j=1; 130 for(int i=1;i<=t;++i) 131 { 132 while(!con[c[j].fr]&&j<=AR){con[c[j].fr]=1;++j;} 133 if(con[son[i].o])continue; 134 for(j;j<=AR;++j) 135 if(c[j].lf>=son[i].d){con[son[i].o]=1;++j;break;} 136 if(!con[son[i].o]){return false;} 137 } 138 return true; 139 } 140 141 int main() 142 { 143 read(n); 144 for(int i=1;i<=n-1;++i) 145 { 146 read(x);read(y);read(z); 147 build(x,y,z);build(y,x,z); 148 maxn+=z; 149 } 150 for(int i=h[1];i;i=e[i].n) 151 { 152 k=e[i].t; 153 dp[k]=dp[1]+1; 154 fa[k]=1; 155 dfs(k,e[i].l,k); 156 } 157 read(m); 158 for(int i=1;i<=m;++i)read(a[i]); 159 l=0;r=maxn; 160 while(l+1<r) 161 { 162 mid=(l+r)>>1; 163 if(tf(mid))r=mid; 164 else l=mid+1; 165 } 166 if(tf(l))printf("%lld\n",l); 167 else printf("%lld\n",r); 168 return 0; 169 }
【二分答案+lca】疫情控制