Luogu-P4438-道路

Posted on 2024-08-13 Edited on 2026-07-18 Word count in article: 2.1k

题目 P4438 [HNOI/AHOI2018] 道路

题目描述

W 国的交通呈一棵树的形状。W 国一共有 $n-1$ 个城市和 $n$ 个乡村，其中城市从 $1$ 到 $n-1$ 编号，乡村从 $1$ 到 $n$ 编号，且 $1$ 号城市是首都。道路都是单向的，本题中我们只考虑从乡村通往首都的道路网络。

对于每一个城市，恰有一条公路和一条铁路通向这座城市。对于城市 $i$，通向该城市的道路（公路或铁路）的起点，要么是一个乡村，要么是一个编号比 $i$ 大的城市。没有道路通向任何乡村。除了首都以外，从任何城市或乡村出发只有一条道路；首都没有往外的道路。从任何乡村出发，沿着唯一往外的道路走，总可以到达首都。

W 国的国王小 W 获得了一笔资金，他决定用这笔资金来改善交通。由于资金有限，小 W 只能翻修 $n-1$ 条道路。小 W 决定对每个城市翻修恰好一条通向它的道路，即从公路和铁路中选择一条并进行翻修。小 W 希望从乡村通向城市可以尽可能地便利，于是根据人口调查的数据，小 W 对每个乡村制定了三个参数，编号为 $i$ 的乡村的三个参数是 $a_i$，$b_i$ 和 $c_i$。假设从编号为 $i$ 的乡村走到首都一共需要经过 $x$ 条未翻修的公路与 $y$ 条未翻修的铁路，那么该乡村的不便利值为：

$$c_i \cdot (a_i + x) \cdot (b_i + y)$$

在给定的翻修方案下，每个乡村的不便利值相加的和为该翻修方案的不便利值。翻修 $n-1$ 条道路有很多方案，其中不便利值最小的方案称为最优翻修方案，小 W 自然希望找到最优翻修方案，请你帮助他求出这个最优翻修方案的不便利值。

输入格式

第一行为正整数 $n$。

接下来 $n - 1$ 行，每行描述一个城市。其中第 $i$ 行包含两个数 $s_i,t_i$。$s_i$ 表示通向第 $i$ 座城市的公路的起点，$t_i$ 表示通向第 $i$ 座城市的铁路的起点。如果$s_i>0$，那么存在一条从第 $s_i$ 座城市通往第 $i$ 座城市的公路，否则存在一条从第 $-s_i$ 个乡村通往第 $i$ 座城市的公路；$t_i$ 类似地，如果 $t_i > 0$，那么存在一条从第 $t_i$ 座城市通往第 $i$ 座城市的铁路，否则存在一条从第 $-t_i$ 个乡村通往第 $i$ 座城市的铁路。

接下来 $n$ 行，每行描述一个乡村。其中第 $i$ 行包含三个数 $a_i,b_i,c_i$，其意义如题面所示。

输出格式

输出一行一个整数，表示最优翻修方案的不便利值。

思路：dp（树形dp）

负数的处理

题中提到，乡村的节点编号为负值。为了避免下标越界，可以把所有负数的 $i$ 加上数组长度 $N$。
此时，$-i \rightarrow N-i$。

dp表

在一个节点上，存在 $3$ 个变量：

当前的节点 $i$
到首都 $1$ 号节点的公路 $ld$
到首都 $1$ 号节点的铁路 $rd$

因此，使用三维的dp表。

$dp[i][ld][rd]$：节点 $i$，距离首都 $ld$ 条公路、$rd$ 条铁路的总不便利值。

为了避免溢出，使用long long类型。

同时，记录不翻修时节点 $i$ 的公路、铁路数 $ldepth[i],rdepth[i]$；记录每个节点的左右子节点 $lson[i],rson[i]$。

状态

初状态：计算所有乡村翻修后的所有可能的不便利值。

也就是，在 $ld \in [0,ldepth[i]], rd \in [0,rdepth[i]]$ 范围内，计算所有的不便利值$dp[i][ld][rd]$。
1
dp[i][ld][rd] = (a[i] + ld) * (b[i] + rd) * c[i];
状态转移方程：对于任意一个城市节点 $i$，都存在大于 $i$ 的左右两个子节点。枚举 $ld,rd$，理由同上。既然从左右两条路中任选一条，所以分两种情况：
- 翻修左路，$lson[i] \rightarrow dp[lson[i]][ld][rd], rson[i] \rightarrow dp[rson[i]][ld][rd+1]$
- 翻修右路，$lson[i] \rightarrow dp[lson[i]][ld+1][rd], rson[i] \rightarrow dp[rson[i]][ld][rd]$
题中所求为最小不便利值，因此应该在上述两种结果中取较小值。
1
2
3
dp[i][ld][rd] = min(
dp[lson[i]][ld][rd] + dp[rson[i][ld][rd + 1]],
dp[lson[i]][ld + 1][rd] + dp[rson[i][ld][rd]]);
注意：因为较小值的子节点是较大值，而这个方程是由子节点推父节点，所以对于所有的城市节点，应该倒序遍历。
末状态：首都的dp值即为结果。因为首都的 $ldepth[1]=rdepth[1]=0$，所以只需要获取 $dp[1][0][0]$ 即可。

25pts WA Code

// template v6
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 40001;
const int M = 41;

ll dp[N][M][M];

int lson[N]; // Highway
int rson[N]; // Railway
int a[N], b[N], c[N];
int ldepth[N]; // total number of highways
int rdepth[N]; // total number of railways

int main() {
    int n;
    cin >> n;
    ldepth[1] = rdepth[1] = 0;
    int t1, t2;
    for(int i = 1; i <= n - 1; i++) {
        cin >> t1 >> t2;
        if(t1 < 0) t1 += N;
        if(t2 < 0) t2 += N;
        lson[i] = t1, rson[i] = t2;
        ldepth[t1] = ldepth[i] + 1;
        rdepth[t1] = rdepth[i];
        ldepth[t2] = ldepth[i];
        rdepth[t2] = rdepth[i] + 1;
    }

    for(int i = N - 1; i >= N - n; i--) {
        cin >> a[i] >> b[i] >> c[i];
    }
    // init villages
    for(int i = N - 1; i >= N - n; i--) {
        for(int j = 0; j <= ldepth[i]; j++) {
            for(int k = 0; k <= rdepth[i]; k++) {
                const int ld = j, rd = k;
                dp[i][ld][rd] = (a[i] + ld) * (b[i] + rd) * c[i];
            }
        }
    }
    // dp
    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j <= ldepth[i]; j++) {
            for(int k = 0; k <= rdepth[i]; k++) {
                const int ld = j, rd = k;
                const int ls = lson[i],
                          rs = rson[i];
                dp[i][ld][rd] = min(
                    dp[ls][ld + 1][rd] + dp[rs][ld][rd],
                    dp[ls][ld][rd] + dp[rs][ld][rd + 1]);
            }
        }
    }
    cout << dp[1][0][0] << endl;
    return 0;
}

为什么会WA

错误原因

看测试点可以知道，在输出为数字的位置会出现负号。

负号？难道long long溢出了吗？

观察数据范围 $1 \le a_i,b_i \le 60$，$1 \le c_i \le 10^9$，发现在相乘过程中只会超出int的范围而不会超过long long的范围。

错误位置

这里直接给出，错误位置是：

1	dp[i][ld][rd] = (a[i] + ld) * (b[i] + rd) * c[i];

为什么会溢出？

C++默认支持的运算是int而不是long long。因此(a[i] + ld) * (b[i] + rd) * c[i]仍然是int类型。

修改

修改也很简单，只需要提前使用long long类型运算即可。

1	dp[i][ld][rd] = 1ll * (a[i] + ld) * (b[i] + rd) * c[i];

这里的1ll就是一个long long类型的常量。

AC Code

// template v6
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7f7f7f7f;

const int N = 40001;
const int M = 41;

ll dp[N][M][M];

int lson[N]; // Highway
int rson[N]; // Railway
int a[N], b[N], c[N];
int ldepth[N]; // total number of highways
int rdepth[N]; // total number of railways

int main() {
    int n;
    cin >> n;
    ldepth[1] = rdepth[1] = 0;
    int t1, t2;
    for(int i = 1; i <= n - 1; i++) {
        cin >> t1 >> t2;
        if(t1 < 0) t1 += N;
        if(t2 < 0) t2 += N;
        lson[i] = t1, rson[i] = t2;
        ldepth[t1] = ldepth[i] + 1;
        rdepth[t1] = rdepth[i];
        ldepth[t2] = ldepth[i];
        rdepth[t2] = rdepth[i] + 1;
    }

    for(int i = N - 1; i >= N - n; i--) {
        cin >> a[i] >> b[i] >> c[i];
    }
    // init villages
    for(int i = N - 1; i >= N - n; i--) {
        for(int j = 0; j <= ldepth[i]; j++) {
            for(int k = 0; k <= rdepth[i]; k++) {
                const int ld = j, rd = k;
                dp[i][ld][rd] = 1ll * (a[i] + ld) * (b[i] + rd) * c[i];
            }
        }
    }
    // dp
    for(int i = n - 1; i >= 1; i--) {
        for(int j = 0; j <= ldepth[i]; j++) {
            for(int k = 0; k <= rdepth[i]; k++) {
                const int ld = j, rd = k;
                const int ls = lson[i],
                          rs = rson[i];
                dp[i][ld][rd] = min(
                    dp[ls][ld + 1][rd] + dp[rs][ld][rd],
                    dp[ls][ld][rd] + dp[rs][ld][rd + 1]);
            }
        }
    }
    cout << dp[1][0][0] << endl;
    return 0;
}