「NOIP 2012」疫情控制

发表于 | | 阅读次数:
字数统计: 1.4k 字

Description

题目链接：Luogu 1084

H 国有 $n$ 个城市由 $n−1$ 条双向道路连通成一棵树，$1$ 号城市是首都，也就是根节点。H 国的首都爆发了传染病。为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），当局决定让军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点。除了首都，任何一个城市都可以建立检查点。

现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在最多一个城市建立检查点。军队移动需要的时间等于经过的道路的长度 $w$。请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

数据范围：$2\le m\le n\le 5\times 10^4$，$0<w<10^9$

Solution

预处理

我们可以发现，节点的深度越小，控制的节点（子树内的节点）越多，所以我们可以贪心地把军队尽量向上提。据此，我们需要把每个点往上的距离预处理，用倍增优化。

二分答案

题目要求的是：军队最大的移动时间的最小值，所以我们可以非常自然地想到二分答案，把问题转化为判定性问题（即是否可以在确定的时间内完成）。

判断合法

根据前面的分析，我们在 $\text{check}$ 的时候要尽量把军队往上走。当二分答案后，设答案为 $x$，这里会有两种情况：军队在 $x$ 的时间内可以到达根节点，军队在 $x$ 的时间内无法到达根节点。

  1. 首先解决军队的上提问题

    • 如果一个军队无法到达根节点，那么他最高的位置一定是最优的，让他待在那里就可以了！

    • 如果一个军队可以得到根节点，那我们求出他到达后还可以走多少时间 $rest$ 以及到达 $1$ 前的儿子 $id$，以便接下来的处理。

  2. 如果还有叶子没有被控制，那我们肯定是把军队调到 $1$ 的某个儿子，因此我们需要处理出 $1$ 的儿子有多少个需要被控制，记录它们和根节点的距离 $dist$。

  3. 最后处理可以到达 $1$ 的军队的去向。

    • 先将这些军队按照 $rest$ 从小到大排序。如果某一个军队的 $id$ 需要被控制，那么就让他不要到达 $1$ 而直接待在 $id$ 就行了。因为如果他不回去，肯定需要别的军队过来控制这个 $id$，这样显然花费时间更大。
    • 再将这些军队按照 $rest$ 从大到小排序，把需要被控制的点按照 $dist$ 从大到小排序。把这两个序列从前往后一一对比就行了！

  4. 是否合法的判断：如果步骤 $3$ 中军队用完了可还有节点需要被控制，那么不合法；否则合法。

时间复杂度：$O(n\log^2 n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=5e4+5,M=1e5+5;
int n,m,tot,a[N],lnk[N],ter[M],nxt[M],val[M],f[N][16];
long long g[N][16];
bool tag[N];
struct data {
    long long val;
    int id;
    bool operator < (const data &rhs) const {
        return val<rhs.val;
    }
} army[N],rest[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],val[tot]=w,lnk[u]=tot;
}
void dfs(int u,int fa) {
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v^fa) f[v][0]=u,g[v][0]=val[i],dfs(v,u);
    }
}
void putTag(int u,int fa) {
    bool res=1,flg=0;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v^fa) putTag(v,u),res&=tag[v],flg=1;
    }
    if(u!=1&&res&&flg) tag[u]=1;
}
void RMQ() {
    for(int j=1;j<=15;++j) for(int i=1;i<=n;++i) {
        f[i][j]=f[f[i][j-1]][j-1];
        g[i][j]=g[i][j-1]+g[f[i][j-1]][j-1];
    }
}
bool check(long long lim) {
    memset(tag,0,sizeof(tag));
    int cntArmy=0,cntRest=0;
    for(int i=1;i<=m;++i) {
        int x=a[i];
        long long sum=0;
        for(int j=15;~j;--j) if(f[x][j]>1&&sum+g[x][j]<=lim) sum+=g[x][j],x=f[x][j];
        if(f[x][0]==1&&sum+g[x][0]<=lim) army[++cntArmy]=data{lim-sum-g[x][0],x};
        else tag[x]=1;
    }
    putTag(1,0);
    for(int i=lnk[1];i;i=nxt[i]) {
        int v=ter[i];
        if(!tag[v]) rest[++cntRest]=data{val[i],v};
    }
    std::sort(army+1,army+cntArmy+1);
    std::sort(rest+1,rest+cntRest+1);
    int j=1;
    for(int i=1;i<=cntArmy;++i) {
        if(!tag[army[i].id]) tag[army[i].id]=1;
        else if(army[i].val>=rest[j].val) tag[rest[j].id]=1;
        while(tag[rest[j].id]&&j<=cntRest) ++j;
    }
    return j>cntRest;
}
int main() {
    scanf("%d",&n);
    long long sum=0;
    for(int u,v,w,i=1;i<n;++i) {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w),add(v,u,w),sum+=w;
    }
    dfs(1,0),RMQ();
    scanf("%d",&m);
    for(int i=1;i<=m;++i) scanf("%d",&a[i]);
    long long l=0,r=sum,ans=-1;
    while(l<=r) {
        long long mid=(l+r)>>1;
        check(mid)?(ans=mid,r=mid-1):l=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}
0%