NOIP2012 D2 T3 疫情控制 洛谷P1084
题目链接：https://www.luogu.org/problemnew/show/P1084
算法：倍增，二分答案，贪心 + 瞎搞。。
背景：上学长的数论课啥也听不懂，于是前去提高组找安慰。不巧碰上了这个题。。蒟蒻整整码了一天。。。调了又一天。。。。最后看的洛谷@beretty的题解。。。。。过了。。。。。。
感谢@beretty。
警告！：代码量3K左右。
思路：
大概分析：
首先，我们需要知道怎样才能控制疫情。（废话。。 ）
通过题意，可以想到在一棵根节点的子树中，越靠近根节点的节点能控制该棵树的叶子节点（边境城市）的个数越多。
（比如在 4 这个节点，可以控制 15 7 11 3 12 2 这几个叶子节点）
？？ 这说明了什么 ？？
通过思考，我们知道如果样例合法，最坏情况也就是将检查站全部设在根节点的儿子上，便能控制疫情。
为何是二分答案？
再来分析一下问题：军队可以同时移动，说明我们的答案是移动时间最长的军队的移动时间。而我们要求最小值，即最大化最小值。
！！！最大化最小值！！！
典型的二分答案的标志。 二分什么？ 当然是时间。
如何check？
上文中提到了（！敲黑板） 越接近根节点的节点控制能力越强。 这说明，我们只需要在规定时间内贪心的把军队向根节点移动，移动的越远越好（不到根节点都可以）。
如何移动? 当然不能暴力的一个一个往上移。这时候 倍增 这种东西就特别好用。我们可以先预处理出来每个节点向上跳$2^j$步是谁，顺便处理出到这个点的距离。
之前的预处理代码：（大佬们请跳过。。）
1 void dfs(int p,int f) 2 { 3 for(int i=head[p];i;i=nex[i]) 4 { 5 int v=to[i]; 6 if(v!=f) 7 { 8 fa[v][0]=p; 9 F[v][0]=val[i]; 10 dfs(v,p); 11 } 12 } 13 }
View Code
倍增预处理代码：
1 void update() 2 { 3 for(int j=1;j<=18;j++) 4 for(int i=1;i<=n;i++) 5 { 6 fa[i][j]=fa[fa[i][j-1]][j-1]; 7 F[i][j]=F[i][j-1]+F[fa[i][j-1]][j-1]; 8 } 9 }
View Code
我们可以让规定时间内能到根节点的部队先全部到根节点，顺便记录它在向上跳的路径中根节点的儿子 $top$ ，以及到根节点时的剩余时间 $rest$。不能到根节点的部队到它能到的地方，打上标记。
重点！！！ 有时候我们会发现，有的子树上没有军队（该子树暂时不能被控制），这时候就需要跨子树（越过根节点）移动部队。！！！这里好难想 可以将所有到根节点的部队按照 $rest$ 从小到大排序，然后看看它在 $rest$ 时间内能不能回到 $top$ ,如果不能，就不让它在根节点呆着，让它移动到 $top$ 去，控制该子树。
操作完毕后，我们将那些没被控制的子树的 $top$ 存好，从大到小排序。再将现在仍在根节点的部队从大到小排个序，看看能否将没被控制的的全部控制。能，返回true，否则返回false。
以下为全部代码：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 const int N = 50005; 6 const int root=1; 7 const int logn = 19; 8 int head[N]; 9 int to[N<<1]; 10 int nex[N<<1]; 11 int val[N<<1]; 12 int cnt,n,m; 13 int fa[N][logn+1]; 14 int top[N]; 15 int tdis[N]; 16 int army[N]; 17 long long F[N][logn+1]; 18 bool pos[N]; 19 int q[N]; 20 bool vis[N]; 21 int cnt_a; 22 void addedge(int a, int b,int v) 23 { 24 nex[++cnt]=head[a]; 25 head[a]=cnt; 26 to[cnt]=b; 27 val[cnt]=v; 28 } 29 void dfs(int p,int f) 30 { 31 for(int i=head[p];i;i=nex[i]) 32 { 33 int v=to[i]; 34 if(v!=f) 35 { 36 fa[v][0]=p; 37 F[v][0]=val[i]; 38 dfs(v,p); 39 } 40 } 41 } 42 void update() 43 { 44 for(int j=1;j<=18;j++) 45 for(int i=1;i<=n;i++) 46 { 47 fa[i][j]=fa[fa[i][j-1]][j-1]; 48 F[i][j]=F[i][j-1]+F[fa[i][j-1]][j-1]; 49 } 50 } 51 void dfs1(int p,int f,int topf,int dist) 52 { 53 top[p]=topf; 54 tdis[p]=dist; 55 bool ft=0; 56 for(int i=head[p];i;i=nex[i]) 57 { 58 int v=to[i]; 59 if(v!=f) 60 { 61 ft=1; 62 dfs1(v,p,topf,dist); 63 } 64 } 65 if(!ft) 66 pos[p]=1; 67 } 68 bool fs; 69 void dfs2(int p,int f) 70 { 71 if(pos[p]) 72 { 73 fs=1; 74 return ; 75 } 76 for(int i=head[p];i;i=nex[i]) 77 { 78 int v=to[i]; 79 if(v!=f&&!vis[v]) 80 { 81 dfs2(v,p); 82 if(fs) 83 return ; 84 } 85 } 86 } 87 bool check2(int p) 88 { 89 fs=0; 90 dfs2(p,fa[p][0]); 91 return fs; 92 } 93 struct node 94 { 95 int up; 96 int rest; 97 }stop[N]; 98 bool cmp1(node a,node b) 99 { 100 return a.rest<b.rest; 101 } 102 bool cmp2(node a,node b) 103 { 104 return a.rest>b.rest; 105 } 106 bool cmp(int a,int b) 107 { 108 return a>b; 109 } 110 bool check(int time) 111 { 112 memset(stop,0,sizeof(stop)); 113 memset(vis,0,sizeof(vis)); 114 memset(q,0,sizeof(q)); 115 cnt_a=0; 116 for(int i=1;i<=m;i++) 117 { 118 int time2=time; 119 int now=army[i]; 120 bool can=0; 121 while(1) 122 { 123 for(int j=18;j>=0;j--) 124 { 125 if(fa[now][j]&&F[now][j]<=time2) 126 { 127 time2-=F[now][j]; 128 now=fa[now][j]; 129 break; 130 } 131 if(j==0||now==1) 132 { 133 can=1; 134 break; 135 } 136 } 137 if(can) 138 break; 139 } 140 if(now==1) 141 { 142 stop[++cnt_a].up=top[army[i]]; 143 stop[cnt_a].rest=time2; 144 } 145 else 146 vis[now]=1; 147 } 148 sort(stop+1,stop+m+1,cmp1); 149 for(int i=1;i<=m;i++) 150 { 151 if(stop[i].rest<tdis[stop[i].up]) 152 { 153 if(!vis[stop[i].up]&&check2(stop[i].up)) 154 { 155 vis[stop[i].up]=1; 156 stop[i].rest=-1; 157 } 158 } 159 } 160 int tail=0; 161 sort(stop+1,stop+m+1,cmp2); 162 for(int i=head[1];i;i=nex[i]) 163 { 164 int v=to[i]; 165 if(!vis[v]&&check2(v)) 166 q[++tail]=val[i]; 167 } 168 sort(q+1,q+tail+1,cmp); 169 for(int i=1;i<=tail;i++) 170 if(stop[i].rest<q[i]) 171 return false; 172 return true; 173 } 174 int main() 175 { 176 int l, r; 177 scanf("%d",&n); 178 for(int i=1;i<n;i++) 179 { 180 int a, b, v; 181 scanf("%d%d%d",&a,&b,&v); 182 r+=v; 183 addedge(a,b,v); 184 addedge(b,a,v); 185 } 186 dfs(1,0); 187 for(int i=head[1];i;i=nex[i]) 188 { 189 int p=to[i]; 190 dfs1(p,1,p,val[i]); 191 } 192 update(); 193 scanf("%d",&m); 194 for(int i=1;i<=m;i++) 195 scanf("%d",&army[i]); 196 int idx=0; 197 for(int i=head[1];i;i=nex[i]) 198 if(to[i]!=1) 199 idx++; 200 if(m<idx) 201 { 202 printf("-1"); 203 return 0; 204 } 205 l=0; 206 int ans; 207 while(l<r) 208 { 209 int mid=(l+r)>>1; 210 if(check(mid)) 211 ans=mid,r=mid; 212 else 213 l=mid+1; 214 } 215 printf("%d",ans); 216 return 0; 217 }
View Code