BZOJ 3836 - [Poi2014]Tourism

#动态规划 #状态压缩动态规划 #树形动态规划

Published on 2017-06-09

题目地址

描述

给定一个 $n(n\le 20000)$ 个点， $m(m\le 25000)$ 条边的无向图，其中在第 $i$ 个点建立旅游站点的费用为 $c_i$ 。在这张图中，任意两点间不存在节点数超过 $10$ 的简单路径。

请找到一种费用最小的建立旅游站点的方案，使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。

分析

好久没有令人耳目一新的题了。

如果没有「任意两点间不存在节点数超过 $10$ 的简单路径」的性质，那么这显然是一个 NP 问题， $n = 20000$ 肯定是做不了的。考虑如何利用这个性质。

不失一般性，我们考虑一个联通块的情况。我们任选一个节点开始 DFS，那么得到的 DFS 树的深度不超过 $10$ ，同时非树边只会是返祖边。

考虑在树上是怎么做的，由于一个点只会被它的父亲和儿子影响，我们记录 $f(u, i)$ 为：满足 $u$ 的子树中的点被覆盖（不包含 $u$ ），且点 $u$ 的状态 $i$ 为的最小代价。若 $i = 0$ ，表示选择了 $u$ ；若 $i = 1$ ，表示没有选择 $u$ ，且 $u$ 未被覆盖；如果 $i = 2$ ，表示没有选择 $u$ ，但 $u$ 已被覆盖。

现在一个点既会被它的子树中的点影响，也会被它到根的路径上的点影响，我们考虑状压树形 DP。

这个 DP 非常厉害，完美的处理了所有的相互影响关系，而且 DP 的顺序非常妙，我只能尽量解释清楚这个 DP 在干什么。

设 $f(u, s)$ 为：满足 $u$ 的子树被覆盖（不包含 $u$ ），且满足 DFS 序比 $u$ 小的点被覆盖（不包含 $u$ 到根的路径上的点），且 $u$ 到根的路径上的每个点的状态为 $s$ 的最小代价。状态 $s$ 中，第 $i$ 位为 $u$ 到根的路径上深度为 $i$ 的点的状态，与树形 DP 类似，状态有 3 种：

选了 $u$
没有选择 $u$ ，且 $u$ 未被覆盖
没有选择 $u$ ，且 $u$ 已被覆盖

由于祖先和儿子之间会互相影响，这个 DP 是在 DFS 中计算的。DFS 到 $u$ 的时候，首先用父亲来更新儿子的 $f(u)$ ：用 $f(\mathrm{fa}(u), s)$ 来刷表。首先考虑 $u$ 不选的情况，如果 $u$ 能够向上到达一个已经选了的点，那么可以更新：

f(u, s + 2 \times 3 ^ {\mathrm{dep}(u)}) \leftarrow f(\mathrm{fa}(u), s)

否则只能更新：

f(u, s + 3 ^ {\mathrm{dep}(u)}) \leftarrow f(\mathrm{fa}(u), s)

再考虑 $u$ 选的情况，此时选择 $u$ ，会导致 $u$ 到根的路径上的一些点的状态从 1 变到 2，设新的状态为 $s'$ ，那么可以更新：

f(u, s') \leftarrow f(\mathrm{fa}(u), s) + c_u

现在只剩下子树对 $u$ 的影响了，我们依次递归处理 $u$ 的每个子树，每次递归完一个子树 $v$ ， $f(u)$ 从子树更新一次

f(u, s) = \min(f(v, s), f(v, s + 2 \times 3 ^ {\mathrm{dep}(v)}))

不难发现这样是正确的，子树会先从 $f(u)$ 更新，这样就继承了之前的点的贡献，计算完子树的答案之后， $f(u)$ 又会从子树更新，这样就处理了子树对 $u$ 到根的路径的贡献，所有相互影响的关系都计算了，显然，最优方案一定会被我们 DP 到，所以这个 DP 是正确的。

我们需要的空间是 $n\times 3^{10}$ 的，无法开下。注意到 DFS 过程中，不会同时有 2 个深度相同的点在递归栈中，所以我们对每个深度开一个 $f(s)$ ，这样就只需要 $10\times 3^{10}$ 的空间，可以开下。

复杂度： $O(n\times 3^{10}\times 10)$ 。

建议对照代码食用。

总结：解法首先利用性质，将问题转换到深度不超过 $10$ 的 DFS 树上。由于父亲儿子之间会相互影响，对每个点记录其到根路径上所有点的信息，先从父亲更新一次，再将结果给子树，再从子树更新一次，这样就巧妙地处理了所有的相互影响关系。

代码

//  Created by Sengxian on 2017/06/09.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 3836 树形状压 DP
#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 * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 20000 + 3, MAX_M = 25000 + 3, MAX_DEP = 10, MAX_POW = 59049, INF = 0x3f3f3f3f;

struct Edge {
    Edge *next;
    int to;
    Edge(Edge *next = NULL, int to = 0) : next(next), to(to) {}
} pool[MAX_M * 2], *pit = pool, *first[MAX_N];

int n, m, c[MAX_N], dep[MAX_N], power[MAX_DEP + 1];
int dp[MAX_DEP][MAX_POW];
bool vis[MAX_N];

inline int bit(int s, int w) {
    return (s / power[w]) % 3;
}

inline void relax(int &a, const int &b) {
    if (b < a) a = b;
}

void dfs(int u) {
    vis[u] = true;
    memset(dp[dep[u]], 0x3f, sizeof dp[dep[u]]);
    if (dep[u] == 0) {
        dp[0][0] = c[u];
        dp[0][1] = 0;
        dp[0][2] = INF;
    } else {
        static bool ok[MAX_N];
        memset(ok, 0, sizeof ok);
        for (Edge *e = first[u]; e; e = e->next)
            if (vis[e->to]) ok[dep[e->to]] = true;
        for (int s = 0; s < power[dep[u]]; ++s) if (dp[dep[u] - 1][s] < INF) {
            bool have = false;
            int newS = s;
            for (int i = 0; i < dep[u]; ++i) {
                have |= ok[i] && bit(s, i) == 0;
                newS += power[i] * (ok[i] && bit(s, i) == 1);
            }

            // 不选
            if (have) relax(dp[dep[u]][s + power[dep[u]] * 2], dp[dep[u] - 1][s]);
            else relax(dp[dep[u]][s + power[dep[u]]], dp[dep[u] - 1][s]);
            // 选
            relax(dp[dep[u]][newS], dp[dep[u] - 1][s] + c[u]);
        }
    }

    for (Edge *e = first[u]; e; e = e->next)
        if (!vis[e->to]) {
            dep[e->to] = dep[u] + 1;
            dfs(e->to);
            for (int s = 0; s < power[dep[u] + 1]; ++s)
                dp[dep[u]][s] = min(dp[dep[u] + 1][s], dp[dep[u] + 1][s + power[dep[u] + 1] * 2]);
        }
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt(), m = readInt();
    for (int i = 0; i < n; ++i) c[i] = readInt();
    for (int i = 0; i < m; ++i) {
        int u = readInt() - 1, v = readInt() - 1;
        first[u] = new (pit++) Edge(first[u], v);
        first[v] = new (pit++) Edge(first[v], u);
    }

    power[0] = 1;
    for (int i = 1; i <= MAX_DEP; ++i) power[i] = power[i - 1] * 3;

    int ans = 0;
    for (int i = 0; i < n; ++i) if (!vis[i])
        dfs(i), ans += min(dp[0][0], dp[0][2]);
    printf("%d\n", ans);

    return 0;
}

BZOJ 3830 - [Poi2014]Freight Codeforces 809E - Surprise me!

Sengxian's Blog

BZOJ 3836 - [Poi2014]Tourism

描述

分析

代码