BZOJ 2525 - [Poi2011]Dynamite

#贪心 #树形贪心
Published on 2016-09-21

题目地址

描述

Byteotian Cave 的结构是一棵 n(n≤300000)n(n\le 300000) 个节点的树，其中某些点上面已经安置了炸药，现在需要点燃 m(m≤n)m(m\le n) 个点上的引线引爆所有的炸药。某个点上的引线被点燃后的 11 单位时间内，在树上和它相邻的点的引线会被点燃。如果一个有炸药的点的引信被点燃，那么这个点上的炸药会爆炸。
求引爆所有炸药的最短时间。

分析

二分答案 tt，则问题转换为，能否在 ≤m\le m 个点上引燃炸药，使得任意炸药到引燃点的距离不大于 tt。
引燃每个点的代价都是相同的，我们考虑树形贪心，我们贪心的引燃炸药，只在需要的时候引燃，怎么操作呢？
记录 fif_i 为 ii 的子树中，最近的引燃点距离 ii 的距离，不存在为 ∞\infty。gig_i 为 ii 的子树中，最远的未被覆盖的炸药点距离 ii 的距离，不存在为 −∞-\infty。
对于以节点 ii 为根的子树，有四种状态：

  1. 这棵子树中存在一个引燃点，这个选择的点的贡献还能继续向上传递，即 fi≤t,gi=−∞f_i \le t, g_i = -\infty。
  2. 这棵子树中存在一个未被覆盖的炸药点，需要某个引燃点去覆盖他，即 fi=∞,gi≥0f_i = \infty, g_i \ge 0。
  3. 这棵子树中既没有能继续向上传递的引燃点也不存在未覆盖的炸药点，即 fi=∞,gi=−∞f_i = \infty, g_i = -\infty。
  4. 这棵子树中既有能继续向上传递的引燃点也有未覆盖的炸药点，即 fi≤t,gi≥0f_i \le t, g_i \ge 0。

如果是第四种情况，说明 ii 的子树中的引燃点覆盖不到炸药点，如果 ii 的子树中的引燃点能够覆盖 ii 的子树外的某些炸药点，那么 ii 子树外能覆盖 ii 的子树中的炸药点的点，也能够覆盖 ii 的子树外的那些炸药点。所以 ii 的子树中的引燃点，归到情况 2。
如何处理子树 ii。首先递归处理子树，然后计算出 fi,gif_i, g_i，一旦 gi=tg_i = t，那么我们立刻在 ii 处放置引燃点，gig_i 变为 −∞-\infty。否则如果 fi+gi≤tf_i + g_i \le t，那么也可以覆盖到 gig_i，gig_i 也变为 −∞-\infty。

最后如果根的 f+g>tf + g > t，根也放置一个引燃点。

我很想证明这个贪心，但是尝试无果，只好感性的理解为「我们只在需要放的时候放，所以最优」。

代码

//  Created by Sengxian on 09/21/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2525 二分 + 树形贪心
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 300000 + 3, INF = 0x3f3f3f3f;
struct edge {
    edge *next;
    int to;
    edge(edge *next = NULL, int to = 0): next(next), to(to) {}
} pool[MAX_N * 2], *pit = pool, *first[MAX_N];

int n, m;
bool have[MAX_N];

int f[MAX_N], g[MAX_N], cnt = 0;

void dfs(int u, int fa, int t) {
    f[u] = INF, g[u] = -INF;
    for (edge *e = first[u]; e; e = e->next) if (e->to != fa) {
        dfs(e->to, u, t);
        f[u] = min(f[u], f[e->to] + 1);
        g[u] = max(g[u], g[e->to] + 1);
    }
    if (have[u]) g[u] = max(g[u], 0);
    if (g[u] + 1 > t) cnt++, f[u] = 0, g[u] = -INF;
    else if (f[u] + g[u] <= t) g[u] = -INF;
}

inline bool judge(int t) {
    cnt = 0;
    dfs(0, -1, t);
    return cnt + (f[0] + g[0] > t) <= m;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < n; ++i) have[i] = ReadInt();
    for (int i = 0; i < n - 1; ++i) {
        static int u, v;
        u = ReadInt() - 1, v = ReadInt() - 1;
        first[u] = new(pit++) edge(first[u], v);
        first[v] = new(pit++) edge(first[v], u);
    }
    int l = -1, r = n;
    while (r - l > 1) {
        int mid = (l + r) >> 1;
        if (judge(mid)) r = mid;
        else l = mid;
    }
    printf("%d\n", r);
    return 0;
}
BZOJ 1122 - [POI2008]账本BBB