ICPC World Finals 2020 ‘S No Problem (树形dp) （k 条不相交路径覆盖最值问题）

TP

题意：

• 用两条线（可以来回走，可以相交，不要求是简单路径）覆盖一颗树，花费为每条边被覆盖的次数乘边权之和。问覆盖这棵树的最小花费是多少？

思路：

• 首先转换一下问题，从任意一个点出发，我们一定能每条边经过两次（标记两次）再回到该点。这样花费的上界就是 两倍的边权和。

• 之后我们再用线（不是题意里的线了）去消除标记，可以发现，经过一条边相当于把该边的标记 -1，一条边的标记至少为 1（不然就不是覆盖这棵树了），这样的线走过的一定是简单路径，如果用两条的话，这两条线一定不会有公共边（否则一条边的标记就会减 2）。

• 致此问题就转换成，如何用两条不公共的简单路径最大化走过的权值。最后答案就是 两倍边权和 - 该最大化值，也就是我们的最小花费。

• 这个思路也可以拓展为用 k 条不公共的简单路径覆盖一棵树能获得的最大值。具体方法看代码。

写法：

• 树形分组背包，神中神的定义

摘自知乎题解：dalao

$Code:$

#include
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))

const int N = 1e5 + 10, M = 1e6 + 10, mod = 1e9 + 7;
int n, m, ki;

int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int x) {
    e[idx] = b, ne[idx] = h[a], w[idx] = x, h[a] = idx++;
}

static vector<int> dfs(int x, int f, int up) {

    //dp[0] = 0;
    //dp[1] 代表 往 x 结点之上延伸 的最长的 一条线段
    //dp[2] 代表 不往 x 结点之上延伸 的最长的 一条线段
    //dp[3] 代表 往 x 结点之上延伸（当然只能延伸一条） 的两条线段
    //dp[4] 代表 不往 x 结点之上延伸 两条线段

    //以此类推 dp[5] 、dp[6] 

    vector<int> dp(up + 1, 0);

    for (int v = h[x]; ~v; v = ne[v]) {
        int to = e[v]; if (to == f)continue;

        auto sub = dfs(to, x, up);//返回数组类型，方便分组背包

        for (int i = up - 1; i >= 0; i--) { //倒序背包，i 可以为 0，j 为 0 无意义
            for (int j = up - i; j >= 1; j--) {

                //可以发现当且仅当 j 下标为奇数时，对应线段在定义上是要往 to 结点之上延伸的
                //也就是说可以获得 x -> to 这条边的权值

                int ww = dp[i] + sub[j] + (j & 1 ? w[v] : 0);
                dp[i + j] = max(dp[i + j], ww);
            }
        }
    }
    return dp;
}

int main() {
    cinios;

    cin >> n;
    mem(h, -1);

    int K = 2;//两条线覆盖

    int ans = 0;
    for (int i = 1; i < n; i++) {
        int a, b, x;
        cin >> a >> b >> x;
        add(a, b, x), add(b, a, x);
        ans += 2 * x;
    }

    auto res = dfs(1, -1, 2 * K);//两倍维度
    int mx = res[2 * K];

    cout << ans - mx;

    return 0;
}
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

模块化的代码真的太漂亮了