题解 P1084 疫情控制

ctq1999 · 2019-10-01 10:03:44 · 题解

传送门

这题开始看了很多题解，也没有看懂，要么太长，要么变量奇怪，所有我写了篇福利文，看不懂找我算账。

题面简述

有一颗树，初始给你一些板子来挡住水流，让你把板子往上提（提的时间为边的长度），水会从根节点流出，最短需要多长时间才不会使水流到叶节点外（即板子也可以放在叶节点上）？

思路

前置知识：邻接表、LCA

类似于lca的方法，倍增预处理出f父亲节点和dis到父亲节点的长度数组。
二分答案。
对于每个当前的lim，把每个军队上提到能够达到的最高位置（最高上提到根节点的子节点），因为越往上，能堵住的子树大小就越大。
对于可以上提到根节点的子节点，再经过根节点后还能行走的军队，存入rest_army数组中，同时求出根每个子节点空闲军队走到根节点后剩余行程最小的编号（restnum和restmin）。
判断根的子节点的空隙情况，存到gap数组中。
贪心。对于rest_army和gap数组进行从大到小排序。这样可以保证贪心的正确性。

详见程序

#include <bits/stdc++.h>

#define MAXN 100010
#define ll long long

using namespace std;

int n, m, tot;
ll restarmy_num, gap_num;

struct edge {
    int to, next;
    int w;
}e[MAXN];//邻接表

int head[MAXN];

int f[MAXN][22];

int garrison[MAXN];//是否驻守
int restnum[MAXN];

ll restmin[MAXN], dis[MAXN][22];

int used[MAXN], army[MAXN]; 

void add(int x, int y, int z) {
    e[++tot].to = y;
    e[tot].w = z;
    e[tot].next = head[x];
    head[x] = tot;
}

void dfs(int x, int fath, ll len) {
    f[x][0] = fath;
    dis[x][0] = len;

    for (int i = 1; i <= 17; i++) {
        f[x][i] = f[f[x][i - 1]][i - 1];
        dis[x][i] = dis[x][i - 1] + dis[f[x][i - 1]][i - 1];
    }

    for (int i = head[x]; i; i = e[i].next) {
        if (e[i].to != fath) dfs(e[i].to, x, e[i].w);
    }
}//这里看不懂可以去学一下LCA最近公共祖先

struct node {
    int id;
    ll rest;
}rest_army[MAXN], gap[MAXN];

int checkok(int x, int fath) {
    bool no_gap = 1;//判断有没有空隙
    bool have_son = 0;//判断有没有子节点
    if (garrison[x]) return 1;//若已被驻守，返回true

    for (int i = head[x]; i; i = e[i].next) {
        if (e[i].to == fath) continue;
        have_son = 1;//有
        if (!checkok(e[i].to, x)) {
            no_gap = 0;//有空隙
            if (x == 1) {
                gap[++gap_num].id = e[i].to;
                gap[gap_num].rest = e[i].w;
            }
            else return 0;
        }
    }

    if (!have_son) return 0;
    else return no_gap;
    //如果没有孩子且没有军队在此驻守，返回false
    //有孩子，有一条空隙则返会false
}

bool cmp(node x, node y) {
    return x.rest > y.rest;
}
bool check(ll lim) {
    restarmy_num = 0;
    gap_num = 0;
    for (int i = 1; i <= n; i++) {
        garrison[i] = 0;
        restnum[i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        used[i] = 0;
    }
    //初始化

    int num, x; 

    for (int i = 1; i <= m; i++) {
        x = army[i];
        num = 0;
        for (int j = 17; j >= 0; j--) {//3. 上提
            if (f[x][j] > 1 && num + dis[x][j] <= lim) {
                num += dis[x][j];
                x = f[x][j];
            }
        }
        if (f[x][0] == 1 && lim - num - dis[x][0] >= 0) {//4. 空闲军队的处理
            rest_army[++restarmy_num].id = i;
            rest_army[restarmy_num].rest = lim - num - dis[x][0];//经过根节点后还能走多远
            if (!restnum[x] || restmin[x] > rest_army[restarmy_num].rest) {
                restnum[x] = i;
                restmin[x] = rest_army[restarmy_num].rest;
            }
        }
        else garrison[x] = 1;//否则就在此节点驻守
    }

    if (checkok(1, 0)) return 1;//5. 求出根节点中有哪些子节点是有空隙到叶节点的，存入gap数组，

    //6. 贪心
    sort(rest_army + 1, rest_army + restarmy_num + 1, cmp);
    sort(gap + 1, gap + gap_num + 1, cmp);//对两个数组从大到小排序，来保证每一步最优

    used[0] = 1;
    int now = 1;
    for (int i = 1; i <= gap_num; i++) {
        if (!used[restnum[gap[i].id]]) {
            used[restnum[gap[i].id]] = 1;
            continue;
        }//如果此节点行程最小的空闲军队没有被只用，那么这个军队直接在此驻守

    while (now <= restarmy_num && (used[rest_army[now].id] || rest_army[now].rest < gap[i].rest)) now++;
        //若不行则遍历一遍，寻找可以经过根节点来到此节点的空闲军队。
        if (now > restarmy_num) return 0;//若遍历完还没有，则返回false
        used[rest_army[now].id] = 1;//标记已使用
    }
    return 1;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, 0, 0);
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) scanf("%d", &army[i]);

    int l = 1, r = 500000;
    ll ans = 0;
    int mid;
    while (l <= r) {//2. 二分答案
        mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;
    }

    cout << ans << endl;
    return 0;
}