洛谷 P1084 NOIp2012提高组 疫情控制 题解【倍增】【贪心】

点击量：172

    脑补了很久的一个题，今天才做出来……

目录

题目描述

H国有$ n$个城市，这$ n$个城市用$ n-1$条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。

 

H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

 

现在，在H国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

 

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

 

输入输出格式

输入格式：

第一行一个整数$ n$，表示城市个数。

 

接下来的$ n-1$行，每行3个整数，$ u,v,w$，每两个整数之间用一个空格隔开，表示从城市$ u$到城市$ v$有一条长为$ w$的道路。数据保证输入的是一棵树，且根节点编号为1。

 

接下来一行一个整数$ m$，表示军队个数。

 

接下来一行$ m$个整数，每两个整数之间用一个空格隔开，分别表示这$ m$个军队所驻扎的城市的编号。

 

输出格式：

一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

 

输入输出样例

输入样例#1：

4 
1 2 1 
1 3 2 
3 4 3 
2 
2 2

输出样例#1：

3

说明

【输入输出样例说明】

第一支军队在2号点设立检查点，第二支军队从2号点移动到3号点设立检查点，所需时间为3个小时。

【数据范围】

保证军队不会驻扎在首都。

对于 20%的数据，$ 2\le n\le 10$；

 

对于 40%的数据，$ 2\le n\le 50,\ 0<w<10^5$；

 

对于 60%的数据，$ 2\le n\le 1000,\ 0<w<10^6$；

 

对于 80%的数据，$ 2\le n\le 10000$；

 

对于 100%的数据，$ 2\le n\le 50000,\ 0<w<10^9$。

题解：

    首先，因为不同的军队可以同时移动，因此答案是移动最远的军队的时间。而我们要求的是最小值，也就是军队移动的最远距离最小，因此可以考虑二分答案。

    有了二分答案，我们就可以知道军队最远能到达哪里。在题目中我们要求每个叶子到根节点的路径上都至少有一个军队，根据贪心，我们要让军队尽可能往上跳。因为不能跳到根节点，所以能跳到根节点的就在根节点的儿子处待命。

    对那些能跳到根节点的军队，可以先把它们删掉，作为游离的军队。因为它们可以去照顾自己的子树或1号节点其他儿子的子树。接着从根节点依次向它的儿子dfs，遇到军队就返回。如果找到叶子节点，就说明这个子树的根（根节点的这个儿子）需要一个游离的军队来防御，标记上，放进数组中。

    我们把游离的军队和需要被防御的节点分别维护在两个数组里，每次把它们按剩余步数和需要步数排序。如果需要防御的节点比军队数还多，直接返回false。如果可能可行，那么循环每个军队，看它去防御哪个节点。根据贪心（田忌赛马？），我们让剩余步数小的尽可能去防御需要步数小的。如果没有一个需要步数比当前剩余步数小的没被防御的军队，就让它去防御自己来自的那棵子树。

    这是排完序的两个数组

    根据贪心，我们前3个都没有问题，直接上配下。到了第4个，发现配不上了；此时有两种决策，一是去防御自己的来源，二是扔掉。要照顾自己的来源也有两种情况，一是自己的来源不需要保护或被保护了，二是自己的来源没有被保护。如果自己的来源不需要保护，那么这个军队就废掉了，因为比他小的都被比它剩余步数更小的保护了，比它大的又保护不了，没有产生额外价值。

    如果自己的来源被保护了，那么它的需要步数一定比当前剩余步数更小，不过它也有可能有自己的来源，这个来源的需要步数可能比现在要大，就可以利用类似二分图匹配的思想让这个被挤掉的去保护它的儿子，就解决了后面一个比较大的需求。

    如果自己的来源没有被保护，就去保护自己的来源，根据上面的描述，这是这个军队唯一可以做出贡献的地方，因此贪心把它的来源状态置为已保护。因为有了这个特例，在第二个数组的计数指针中，如果指针指到的元素已经被通过某种途径保护了，直接让指针后移。

    预处理用倍增计算出向上跳2的多少次方次需要的距离与目的地。

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::sort;
long long f[51000][18];//倍增的距离
int fa[51000][18];//倍增的位置
struct edge
{
    int n,v,nxt;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){nxt=-1;}
}e[101000];
int head[51000],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);
    head[to]=ecnt;
}

void dfs(int x)//看这棵子树有没有危险
{
    for(int i=head[x];~i;i=e[i].nxt)
        if(!fa[e[i].n][0])
        {
            fa[e[i].n][0]=x;
            f[e[i].n][0]=e[i].v;
            dfs(e[i].n);
        }
}
int n,m;
void init()
{
    for(int i=1;i<=16;i++)
        for(int j=1;j<=n;j++)
        {
            fa[j][i]=fa[fa[j][i-1]][i-1];
            f[j][i]=f[j][i-1]+f[fa[j][i-1]][i-1];
        }
}

struct troop
{
    int n;
    long long dis;
    troop(int n,long long dis)
    {
        this->n=n;
        this->dis=dis;
    }
    troop(){}
    friend bool operator <(troop a,troop b)
    {
        return a.dis<b.dis;
    }
}t[51000];//可用的军队
troop need[51000];//需要保护的儿子点
long long rh[51000];
long long h[51000],up[51000];
//有哪些军队 已经走了多少步
bool ava[51000];//没上去的有哪些军队
int prot[51000];//是否被保护
bool Dfs(int x)
{
    if(prot[x])
        return true;
    int flag=0;
    bool ans=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=fa[x][0])
        {
            flag=1;
            ans&=Dfs(e[i].n);
        }

    return ans&flag;
}
int to[51000];//编号为i的军队去保护了谁
int pp[51000];//编号为i的need是否已被保护
bool check(long long x)
{
    for(int i=1;i<=m;i++)
        h[i]=rh[i];
    memset(ava,1,sizeof(ava));
    memset(pp,0,sizeof(pp));
    memset(to,0,sizeof(to));
    memset(prot,0,sizeof(prot));
    memset(up,0,sizeof(up));
    int cnt=0,cnt1=0;//有多少个军队，有多少需要保护的节点
    for(int i=16;i>=0;i--)
        for(int j=1;j<=m;j++)
            if(fa[h[j]][i]!=1&&f[h[j]][i]+up[j]<=x)//不能到1号节点
            {
                up[j]+=f[h[j]][i];
                h[j]=fa[h[j]][i];
            }
    for(int i=1;i<=m;i++)
        if(fa[h[i]][0]==1)
            if(up[i]+f[h[i]][0]<=x)//如果能到1号，就设为游离的军队
            {
                t[++cnt]=troop(h[i],x-up[i]-f[h[i]][0]);
                ava[i]=0;
            }
    for(int i=1;i<=m;i++)
        if(ava[i])
            prot[h[i]]=1;//如果根节点的儿子安全，就不用保护
    for(int i=head[1];~i;i=e[i].nxt)
        if(!Dfs(e[i].n))
            need[++cnt1]=troop(e[i].n,f[e[i].n][0]);//需要保护的节点
    if(cnt1>cnt)//军队不够保护
        return false;
    std::sort(t+1,t+1+cnt);
    std::sort(need+1,need+1+cnt1);
    int tt=1;//现在从前到后保护几个了
    for(int i=1;i<=cnt;i++)
    {
        if(tt>cnt1)//已经保护完了
            return true;
        while(pp[need[tt].n])//如果被通过某种途径保护，就继续
            tt++;
        if(t[i].dis>=need[tt].dis)
        {
            to[i]=need[tt].n;
            pp[need[tt].n]=1;
            tt++;
        }
        else
        {
            if(to[need[tt].n]&&need[to[need[tt].n]].dis<=t[i].dis)
            {
                pp[need[tt].n]=1;
                tt++;
            }
            else
                pp[t[i].n]=1;
        }
    }
    while(pp[need[tt].n])//注意这里可能会有后面几个全部被前面的保护，因此看tt最终能到哪里（没有这个处理是90分，过不了#1）
        tt++;
    return tt>cnt1;
}

int main()
{
    int u,v,w;
    long long mx=0;
    memset(head,-1,sizeof(head));
    fa[1][0]=1;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        mx+=w;//最长时间肯定是所有边长之和
    }
    dfs(1);
    init();
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        scanf("%d",&rh[i]);
    long long l=0,r=mx+1,mid;
    while(l<r)
    {
        mid=(l+r>>1);
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }
    printf("%lld\n",l);
    return 0;
}