题解 P1084 【疫情控制】

tomtom · 2019-10-20 10:46:15 · 题解

疫情控制

题面描述

luogu链接

题解

• 关键语句：请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。稍微学过语文的同学一看就知道，这是一道题目需要二分答案。稍微看看代码：

• 我们二分最长时间。贪心的想，在长度mid的限制下，每一支军队尽量地往深度浅的地方跳显然是最优的（因为可以覆盖更多的节点）。我们用倍增优化这个向上跳的过程。每个军队跳完之后，我们标记相应的节点已被覆盖。

• 但是题目远不止这么简单。一支军队若是在限制内已经跳到了根节点的子节点，同时他依然有闲情逸志绕过跟节点覆盖还没有被覆盖的跟节点的子节点。我们取消对这些军队的标记，并且把他们额外保存下来（用一个手写的队列貌似非常方便）。保存时要注意同时记录下他们额外可以走的路程与本来可以覆盖的节点（在不越过根节点的情况下）。接下来有一个非常巧妙（但同时也很自然）的操作，将那些有闲情逸志的军队以剩余路程为第一关键字从小到大排序。并且记录下还没有被覆盖的根的子节点与他们和根节点的距离，并按照距离从小到大排序。我们从头到尾扫描这些军队，按照如下方法贪心：

  1. 如果当前军队原来管辖的节点没有被覆盖，那么这支军队选择不越过根节点，而是守在原来的节点上。因为我们是按照剩余路程进行排序的，所以可以证明这种贪心一定最优。
  2. 否则，我们从未被覆盖的节点中选择最合适的与该军队配对。 这一段实现看代码。

• 进行了以上操作之后，扫一遍，若还存在没有被覆盖的根的子节点，则判定这个mid不合法。

看看代码吧：

#prag\
ma GCC optimize("Ofast")
#include<bits/stdc++.h>

const int N = 5e4 + 3;

inline int read()
{
    int s = 0,f = 1; char ch;
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) s = s * 10 + ch - '0',ch = getchar();
    return s * f;
}

typedef std::pair<int,int> pzk;

std::queue<int> q;
pzk stora0[N],stora1[N]; /*两个队列*/

int ver[N << 1],nxt[N << 1],head[N],edge[N << 1],tot = 0;

inline void add(int x,int y,int z)
{
    ver[++tot] = y,edge[tot] = z,nxt[tot] = head[x],head[x] = tot;
}

int dis[N][20],t,fa[N][20],tag[N],tail0,tail1,n,m,
    cities[N],ans{-1},left{INT_MAX},right,mid;

/*倍增预处理*/
inline void prepare()
{
    t = log2(n) + 1;
    q.push(1);
    while(q.size()) {
        int x = q.front(); q.pop();
        for(int i = head[x];i;i = nxt[i]) {
            if(ver[i] == 1 || dis[ver[i]][0]) continue;
            fa[ver[i]][0] = x,dis[ver[i]][0] = edge[i];
            for(int j = 1;j <= t;j++) {
                fa[ver[i]][j] = fa[fa[ver[i]][j - 1]][j - 1];
                dis[ver[i]][j] = dis[fa[ver[i]][j - 1]][j - 1] +
                    dis[ver[i]][j - 1];
            }
            q.push(ver[i]);
        }
    }
}

/*倍增向上跳*/
inline void jump(int idx,int cons)
{
    /*FIXME*/
    for(int i = t;i >= 0;i--)
        if(fa[idx][i] > 1 && cons - dis[idx][i] >= 0) {
            cons -= dis[idx][i];
            idx = fa[idx][i];
        }
    if(cons - dis[idx][0] > 0 && fa[idx][0] == 1)
        stora0[++tail0] = {cons - dis[idx][0],idx};
    else tag[idx] = 1;
}

/*进行初步染色之后，上传标记到根节点的子节点，以便后面的判定。*/
void paint(int x,int fa)
{
    if(tag[x]) return;

    bool flag = 1,has = 0;
    for(int i = head[x];i;i = nxt[i]) {
        if(ver[i] == fa) continue;
        paint(ver[i],x);
        has = 1,flag &= tag[ver[i]];
    }
    tag[x] = flag & has;
}

/*没什么好说的*/
inline bool check(int cons)
{
    for(int i = 1;i <= n;i++) tag[i] = 0;
    tail0 = 0,tail1 = 0;
    for(int i = 1;i <= m;i++) jump(cities[i],cons);

    paint(1,0);
    for(int i = head[1];i;i = nxt[i]) if(!tag[ver[i]])
        stora1[++tail1] = {edge[i],ver[i]};

    std::sort(stora0 + 1,stora0 + 1 + tail0);
    std::sort(stora1 + 1,stora1 + 1 + tail1);

    int ptr = 1;
    for(int i = 1;i <= tail0;i++) {
        if(!tag[stora0[i].second])
            tag[stora0[i].second] = 1;
        else if(ptr <= tail1 && stora0[i].first >= stora1[ptr].first)
            tag[stora1[ptr].second] = 1; /*FIXME*/
        while(ptr <= tail1 && tag[stora1[ptr].second])
            ptr++;
    }
    return ptr > tail1;
}

inline void chkMin(int& x,int y)  {x = std::min(x,y);}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("army.in","r",stdin);
    freopen("army.out","w",stdout);
#endif
    n = read();
    for(int i = 1,u,v,w;i < n;i++) {
        u = read(),v = read(),w = read();
        add(u,v,w),add(v,u,w);

        chkMin(left,w),right += w;
    }

    m = read();
    for(int i = 1;i <= m;i++) *(cities + i) = read();

    prepare();

    while(left <= right) {
        mid = (left + right) >> 1;
        if(check(mid)) right = mid - 1,ans = mid;
        else left = mid + 1;
    }

    printf("%d",ans);

    exit(0);
}