题解 P1084 【疫情控制】

· · 题解

题目链接

这题思维难度较高 我觉得是好题 故写下此题解 顺便加深对此题的理解

0.特别说明

本篇题解中“堵住”是指某一结点上有军队或者它的子结点被“堵住”的状况。

“堵住”整棵树则是根节点被堵住的状况。

做此题前需要先掌握：贪心 二分答案 倍增 基本图论知识

1.题目分析

(1 解题思路

这题中求移动时间最长的军队的最短军队 所以我们果断用二分答案。至于r的大小...把道路长度全都加一遍 就是了

(2 有关check函数

如何判断在mid时间内军队能堵住整棵树？ 首先我们知道的是，军队的在树中的深度越低越好。因为深度越低，子树越大，能控制的点就越多。那么我们让军队尽可能地在mid时间内往上跳。由于此题是n个点n-1条边，所以每个点都只有一个祖先。如果要往上跳的话，就是在一条链上跳，所以我们可以用倍增。

跳完之后，军队可以分2种：1.无法跳到根结点的 对于这种，我们直接把它所在的点和它的子树“锁住”，就不用管了。 2.能跳到根结点的。当军队跳到根结点时，它可能可以去根结点的其他子结点。

我们处理完军队之后，可以看一下当只有第1种军队时，这棵树有没有被堵住。如果被堵住的话，就没有第2种军队什么事了。但是当这棵树没有被堵住时...我们可以把根结点的所有子结点都看一下有没有被堵住，如果没有堵住的话，我们可以派第2种军队去堵住这些点。派遣军队的时候，我们可以用贪心的策略，当根结点和子结点间的道路比较短时，我们可以派剩余时间比较短的军队去，反之则派剩余时间长的军队去。

当第2种军队全部派遣完后，你需要看一下是不是根节点的所有子结点全被堵住了。如果是的话，在mid时间内军队能堵住整棵树。

(3 如何判断-1

很简单，你只需要看一下深度为2的点是否超过m个。如果是的话，军队太少，不可能堵住整棵树。

2.坑点

对于有的第二种军队，它直接跳到根结点的子结点就好了。（前提是子结点没有被堵住） 至于如何解决这个问题，代码第93行有写。

此题码量120行左右但是我写出了140行，粗心一点的话bug会很多....

3.代码

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=50005;
struct edge
{
    int next,to,val;
}e[N*2];
struct take
{
    int pos,rest;
}a[N],b[N];
int f[N][21],cnt,dis[N][21],head[N],army[N],m,used[N],vis[N],dep[N];
void add(int x,int y,int z)
{
    e[++cnt].to=y;
    e[cnt].val=z;
    e[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for(int i=1;i<=20;++i)
    {
        f[x][i]=f[f[x][i-1]][i-1];
        dis[x][i]=dis[f[x][i-1]][i-1]+dis[x][i-1];
    }
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=fa)
        {
            f[v][0]=x; dis[v][0]=e[i].val;
            dfs(v,x);
        }
    }
}
void look(int x,int fa)
{
    int flag=1;
    if(used[x]) return;
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v!=fa)
        {
            flag=0;
            look(v,x);
            if(!used[v]) return;
        }
    }
    if(!flag) used[x]=1;
}
bool cmp(take x,take y)
{
    return x.rest<y.rest;
}
bool check(int x)
{
    memset(used,0,sizeof(used));
    memset(vis,0,sizeof(vis));
    int sizea=0,sizeb=0;
    for(int i=1;i<=m;++i) //用倍增跳 
    {
        int p=army[i],cost=0;
        for(int j=20;j>=0;--j)
            if(cost+dis[p][j]<=x && f[p][j]>1)
            {
                cost+=dis[p][j];
                p=f[p][j];
            }
        if(f[p][0]==1 && cost+dis[p][0]<=x) //第二种军队
        {
            a[++sizea].pos=p;
            a[sizea].rest=x-cost-dis[p][0];
        }
        else used[p]=1;
    }   
    sort(a+1,a+sizea+1,cmp);
    for(int i=head[1];i;i=e[i].next) 
    {
        look(e[i].to,1);
        if(!used[e[i].to])
        {
            b[++sizeb].pos=e[i].to;
            b[sizeb].rest=e[i].val;
        }
    }
    sort(b+1,b+sizeb+1,cmp);//贪心策略
    int j=1;
    for(int i=1;i<=sizea;++i) 
    {
        if(!vis[a[i].pos] && !used[a[i].pos]) vis[a[i].pos]=1; //第93行代码 直接跳到子结点上
        else if(a[i].rest>=b[j].rest)  vis[b[j].pos]=1; 
        while(j<=sizeb && vis[b[j].pos])
            ++j;
        if(j>sizeb) return 1; 
    }
    return 0;
}
int read()
{
    int x=0; char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x;
}
int main()
{
    int n,l=0,r=0;
    n=read();
    for(int i=1;i<n;++i)
    {
        int x,y,z;
        x=read(); y=read(); z=read();
        add(x,y,z); add(y,x,z);
        r+=z;
    }
    dfs(1,0);
    m=read();
    for(int i=1;i<=m;++i)
        army[i]=read();
    int ans=0,sum=0;
    for(int i=1;i<=n;++i)
        if(dep[i]==2) ++sum;
    if(sum>m)
    {
        cout<<-1;
        return 0;
    }
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid-1; ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}