分析题意与解题方法

题目解析

题目要求在给定的树形结构中选择若干个城市建造消防站，使得满足以下条件：

1.每个城市要么有自己的消防站，要么到最近消防站的距离不超过其允许的最大距离 $D(K)$。 2.最小化建造消防站的总成本 $\sum W(K)$。

这是一个经典的树形动态规划问题。我们可以通过以下步骤解决：

解题方法

数据结构

1.图的存储
使用邻接表存储树形结构，edge 数组用于记录边的信息，head 数组记录每个节点的出边起点。

2.状态定义
定义状态 dp[u][i] 表示以节点 $u$ 为根的子树中，将消防站建在节点 $i$ 的最小成本。

3.辅助变量

• dis[u]：从节点 $u$ 到其子树中某个节点 $i$ 的最短距离。
• best[u]：以节点 $u$ 为根的子树中，建造消防站的最小成本。

算法流程

1.构建图
读取输入并构造邻接表。

2.深度优先搜索 (DFS)
从根节点开始递归遍历整棵树：

• 对于每个节点 $u$，计算其所有子树中消防站的最小成本。
• 对于每个子树中的节点 $i$，更新 dp[u][i]：
  • 如果节点 $i$ 的距离超过允许的最大距离 $D(u)$，则 dp[u][i] = inf。
  • 否则，计算当前节点的成本加上子树中其他节点的成本。
• 更新 best[u] 为子树中所有可能情况的最小值。

3.输出结果
对于每个测试用例，输出根节点对应的 best[1]。

时间复杂度

• 图的构造：$O(N)$。
• 深度优先搜索：每个节点最多被访问一次，且每次访问涉及最多 $N$ 个子节点，因此时间复杂度为 $O(N^2)$。
• 总体时间复杂度：$O(T \cdot N^2)$，其中 $T$ 是测试用例数量。

标程

以下是基于上述分析的代码实现：

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 1e3 + 5; // 最大节点数
const int inf = 0x3f3f3f3f; // 定义无穷大

int T, n, cnt, head[maxn], w[maxn], d[maxn], dp[maxn][maxn], dis[maxn];
int best[maxn];

// 边结构体
struct node {
    int v, w, nex; // 目标节点，边权，下一条边
} edge[maxn << 1]; // 边数组

// 添加边
void adde(int u, int v, int w) {
    edge[++cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

// 获取从节点 u 到子树中各节点的距离
void getdis(int u, int fa, int len) {
    dis[u] = len;
    for (int i = head[u]; i; i = edge[i].nex) {
        int v = edge[i].v;
        if (v == fa) continue;
        getdis(v, u, len + edge[i].w);
    }
}

// 深度优先搜索
void dfs(int u, int fa) {
    for (int i = head[u]; i; i = edge[i].nex) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
    }

    getdis(u, 0, 0); // 从节点 u 开始计算子树中各节点的距离
    best[u] = inf; // 初始化最佳成本为无穷大

    for (int i = 1; i <= n; ++i) { // 枚举子树中的节点 i
        if (dis[i] > d[u]) // 如果距离超过允许的最大距离
            dp[u][i] = inf;
        else { // 否则计算当前节点的成本
            dp[u][i] = w[i];
            for (int j = head[u]; j; j = edge[j].nex) {
                int v = edge[j].v;
                if (v == fa) continue;
                dp[u][i] += min(best[v], dp[v][i] - w[i]); // 累加子树中其他节点的成本
            }
        }
        best[u] = min(best[u], dp[u][i]); // 更新最佳成本
    }
}

int main() {
    scanf("%d", &T); // 读取测试用例数量
    while (T--) {
        scanf("%d", &n); // 读取节点数
        cnt = 0; // 初始化边计数器
        for (int i = 1; i <= n; ++i)
            head[i] = 0; // 清空头指针
        for (int i = 1; i <= n; ++i)
            scanf("%d", &w[i]); // 读取建造消防站的成本
        for (int i = 1; i <= n; ++i)
            scanf("%d", &d[i]); // 读取最大允许距离
        for (int i = 1; i < n; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w); // 读取边的信息
            adde(u, v, w); // 添加边
            adde(v, u, w);
        }
        dfs(1, 0); // 从根节点开始 DFS
        printf("%d\n", best[1]); // 输出结果
    }
    return 0;
}