九头龙问题题解

问题分析

本题是一个树形动态规划问题，需要将$N$个果子分配给$M$个头，其中大头必须吃掉恰好$K$个果子且必须包含最大的果子（编号为$1$的果子）。我们需要最小化九头龙吃树枝的难受值总和。

关键观察

1. 树结构：果子通过树枝连接形成一棵树，根节点是编号为$1$的最大果子。

2. 难受值计算规则：

   • 如果两个相邻果子被同一个头吃掉，那么这段树枝的难受值会被计入
   • 如果两个相邻果子被不同头吃掉，那么这段树枝不会被吃掉（难受值为$0$）

3. 约束条件：

   • 大头必须吃掉恰好$K$个果子
   • 每个头至少吃一个果子
   • 总共$M$个头需要$M$组果子

算法思路

状态设计

使用树形DP，定义状态：

• f[x][j][0]：在以$x$为根的子树中，大头吃了$j$个果子，且节点$x$不是被大头吃掉时的最小难受值
• f[x][j][1]：在以$x$为根的子树中，大头吃了$j$个果子，且节点$x$是被大头吃掉时的最小难受值

状态转移

对于节点$x$和它的子节点$y$，考虑四种情况：

1. $x$不是大头吃，$y$不是大头吃

   • 如果$M = 2$，那么$x$和$y$必须被不同的头吃掉，难受值为$w[x][i]$
   • 如果$M > 2$，那么$x$和$y$可以被同一个非大头吃掉，难受值为$0$

2. $x$不是大头吃，$y$是大头吃

   • $x$和$y$被不同头吃掉，难受值为$0$

3. $x$是大头吃，$y$不是大头吃

   • $x$和$y$被不同头吃掉，难受值为$0$

4. $x$是大头吃，$y$是大头吃

   • $x$和$y$被同一个头（大头）吃掉，难受值为$w[x][i]$

转移方程

对于每个子节点$y$：

// x不是大头，y不是大头
if (M == 2) {
    f[x][j][0] = min(f[x][j][0], temp[j-t][0] + min(f[y][t][0] + w[x][i], f[y][t][1]));
} else {
    f[x][j][0] = min(f[x][j][0], temp[j-t][0] + min(f[y][t][0], f[y][t][1]));
}

// x是大头，y任意
f[x][j][1] = min(f[x][j][1], temp[j-t][1] + min(f[y][t][0], f[y][t][1] + w[x][i]));

可行性检查

在开始DP之前，先检查是否满足基本条件：

if (n - k < m - 1) {
    cout << -1 << endl;
    return 0;
}

这是因为：大头吃了$K$个果子，剩下的$N-K$个果子要分配给$M-1$个头，每个头至少一个果子，所以必须满足$N-K ≥ M-1$。

代码实现详解

#include <bits/stdc++.h>
using namespace std;

vector<int> g[305];  // 邻接表存储树的边
vector<int> w[305];  // 存储边的权重（难受值）
int f[305][305][2];  // DP数组
int n, m, k;
int temp[305][2];    // 临时数组，用于辅助DP

void dp(int x, int fa) {
    // 初始化：x节点单独考虑时
    f[x][0][0] = 0;  // x不是大头吃，大头吃0个果子
    f[x][1][1] = 0;  // x是大头吃，大头吃1个果子
    
    // 遍历所有子节点
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (y == fa) continue;
        
        dp(y, x);  // 递归处理子节点
        
        // 保存当前状态
        for (int j = 0; j <= k; j++) {
            temp[j][0] = f[x][j][0];
            temp[j][1] = f[x][j][1];
            f[x][j][0] = f[x][j][1] = 0x3f3f3f3f;  // 重置为无穷大
        }
        
        // 状态转移
        for (int j = k; j >= 0; j--) {          // 当前x子树中大头吃的果子数
            for (int t = 0; t <= j; t++) {      // 子节点y子树中大头吃的果子数
                // 情况1：x不是大头吃
                if (m == 2) {
                    // 只有两个头，x和y如果都不是大头吃，必须被不同的头吃
                    f[x][j][0] = min(f[x][j][0], 
                        temp[j-t][0] + min(f[y][t][0] + w[x][i], f[y][t][1]));
                } else {
                    // 超过两个头，x和y如果都不是大头吃，可以被同一个非大头吃
                    f[x][j][0] = min(f[x][j][0], 
                        temp[j-t][0] + min(f[y][t][0], f[y][t][1]));
                }
                
                // 情况2：x是大头吃
                f[x][j][1] = min(f[x][j][1], 
                    temp[j-t][1] + min(f[y][t][0], f[y][t][1] + w[x][i]));
            }
        }
    }
}

int main() {
    cin >> n >> m >> k;
    
    // 可行性检查
    if (n - k < m - 1) {
        cout << -1 << endl;
        return 0;
    }
    
    memset(f, 0x3f, sizeof(f));
    
    // 读入树结构
    for (int i = 1; i < n; i++) {
        int u, v, z;
        cin >> u >> v >> z;
        g[u].push_back(v);
        g[v].push_back(u);
        w[u].push_back(z);
        w[v].push_back(z);
    }
    
    dp(1, 0);  // 从根节点1开始DP
    
    if (f[1][k][1] >= 0x3f3f3f3f) {
        cout << -1 << endl;
    } else {
        cout << f[1][k][1] << endl;
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \times K^2)$，其中$N \leq 300$，$K \leq 300$，在可接受范围内
• 空间复杂度：$O(N \times K)$

样例分析

对于样例输入：

8 2 4
1 2 20
1 3 4  
1 4 13
2 5 10
2 6 12
3 7 15
3 8 5

最优解为$4$，对应策略是：

• 大头吃果子：$1$, $3$, $7$, $8$
• 小头吃果子：$2$, $4$, $5$, $6$

这样只有连接$1$和$3$的树枝（难受值$4$）被大头吃掉，其他树枝要么不被吃，要么因为连接不同头的果子而被弄断（难受值$0$）。