[NOIP2012]疫情控制 贪心 二分

时间:2023-01-23 19:16:20

题面:[NOIP2012]疫情控制

题解:

  大体思路很好想,但是有个细节很难想QAQ

  首先要求最大时间最小,这种一般都是二分,于是我们二分一个时间,得到一个log。

  然后发现一个军队,越往上走肯定可以控制的叶节点越多,因此我们在时间范围内尽量向上走,又得到一个log了。

  如果一个军队走到根后还有多余时间,那它就有可能走到根的其他儿子去帮助其他子树。

  然后为了尽可能覆盖多的子树,显然应该要用剩余时间少的军队,对应走过去代价小的子树,所以sort一下就可以了?

  然而还有一种情况,那就是一个点从它的子树出发到了root,万一最后需要回到它自己那个子树,直接做就把代价算了2次,这样就可能导致本来可以不花代价就回到原来的子树的,但我们却花了双倍代价。。。。于是可能就把一个合法的时间判成不合法了。

  所以应该怎么做?

  其实只需要在 每个子树中可以走出去帮助其他子树的军队 里面选一个剩余时间最少的,走出去不能回来的军队守护自己就可以了(前提是自己还需要守护)。

  可以证明,这样肯定是最优的。

  因为如果把所有军队都提上去的话,意味这你要用军队x来帮助其他子树,同时意味着要从其他子树选一个军队y来帮助它。那么观察到既然军队x出来后无法回去,却可以帮助某个子树u,因此到这个被帮助的子树u的代价要比回去的代价小。所以如果我们用军队x来守护自己所在的子树,那么原本从其他子树中选出来帮助它的军队y就可以去守护子树u,因为子树u代价比当前子树小,因此子树u一定可以被军队y守护到。

  所以肯定不会变劣。

  写的时候还有一些细节,,,

 #include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 51000
#define ac 101000
#define LL long long int n, m, num, cnt, rnt;
LL all;
int Head[AC], Next[ac], date[ac], tot;
int p[AC], father[AC][];
LL st[AC][], have[AC], len[ac];
bool z[AC], used[AC], vis[AC]; struct node{
int x;
LL rest;
friend bool operator < (node a, node b){
return a.rest < b.rest;
}
}s[AC], son[AC]; inline int read()
{
int x = ;char c = getchar();
while(c > '' || c < '') c = getchar();
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x;
} inline void add(int f, int w, int S)
{
date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot, len[tot] = S;
date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot, len[tot] = S;
} void pre()
{
n = read();
for(R i = ; i < n; i ++)
{
int a = read(), b = read(), c = read();
add(a, b, c), all += c;
}
father[][] = ;//父亲设为自己,防止子树里面的点跳到0
m = read();
for(R i = ; i <= m; i ++) p[i] = read();
} void dfs1(int x)//预处理倍增数组 get: st father have son
{
vis[x] = true;
for(R i = ; i <= ; i ++)
{
father[x][i] = father[father[x][i - ]][i - ];
st[x][i] = st[x][i - ] + st[father[x][i - ]][i - ];
}
int now;
for(R i = Head[x]; i; i = Next[i])
{
now = date[i];
if(vis[now]) continue;
if(x == ) son[++ num] = (node){now, len[i]};
father[now][] = x, st[now][] = len[i];
have[now] = have[x] + len[i], dfs1(now);//记录下从root到now的距离
}
} void dfs2(int x)//找到哪些节点还没有被控制
{
if(z[x]) return ;
int now;bool done = true, flag = false;
for(R i = Head[x]; i; i = Next[i])
{
now = date[i];
if(now == father[x][]) continue;
dfs2(now), flag = true;
if(!z[now]) done = false;//如果儿子里面有一个不合法的,这个节点就不合法
}//不能直接return,因为1号节点一般都不合法,但其他儿子还要标记的,,,
if(flag) z[x] = done;//否则所有儿子都合法,那这个点就合法,但是如果这个点是叶子,,,就不能平白无故打标记了
} bool check(int mid)//判断这个时间是否合法
{
cnt = rnt = ;
memset(z, , sizeof(z));
for(R i = ; i <= m; i ++)
{
int x = p[i], now = ;
for(R j = ; j >= ; j --)
if(father[x][j] != && now + st[x][j] <= mid)
now += st[x][j], x = father[x][j];//记得要先加后跳
if(have[x] >= mid - now) z[x] = true;//无法到达别的子树
else s[++ cnt] = (node){x, mid - now};//可以到达
}
dfs2();
//sort(s + 1, s + cnt + 1);
for(R i = ; i <= cnt; i ++)//分配一个不能回来的给当前子树
if(s[i].rest < * have[s[i].x] && !z[s[i].x]) z[s[i].x] = true;
else s[++ rnt] = s[i], s[rnt].rest -= have[s[i].x];//提到root的同时要加上去root的代价
sort(s + , s + rnt + );//排序。
int l = ;
for(R i = ; i <= num; i ++)//剩下的从小到大依次匹配
{
if(z[son[i].x]) continue;
while(s[l].rest < son[i].rest && l <= rnt) ++ l;
if(l > rnt) return false;
++ l;//把这个用了
}
return true;
} void half()//二分时间
{
if(num > m) {printf("-1\n"); return ;}//如果root儿子数大于军队数,那么永远不可能全部覆盖
sort(son + , son + num + );
int l = , r = all, mid;
while(l < r)
{
mid = (l + r) >> ;
if(check(mid)) r = mid;
else l = mid + ;
}
printf("%d\n", l);
} int main()
{
freopen("in.in", "r", stdin);
pre();
dfs1();
half();
fclose(stdin);
return ;
}