P8817

· · 题解

最初写于 2022 年 10 月，于 2026 年 10 月更新。删减了代码中无用的信息。

欢迎您到我的博客中查看本文，谢谢！

下文中，u 和 v 之间可达意为 u 和 v 之间可以经过不多于 k 次转车到达，即 u 到 v 的距离不多于 k + 1（这里 +1 的细节请仔细看题）。

注意，为方便，后文定义自己和自己不可达。

观察数据范围，n^2 可过，已经足够处理出每个点对之间的距离了。因此首先应该采用 bfs，n^2 计算任意点对之间的距离，以及它们是否可达。这是一个很重要的信息，看完数据范围，有经验的算法竞赛选手应该能立刻明确整张图的点对距离信息完全可知且容易求解。

注意：对于满足边权全为 1 的图，单源最短路可以做到 \mathcal{O}(n) 的复杂度（采用 bfs）；

对于满足边权只有 0，1 两种的图，单源最短路也可以做到 \mathcal{O}(n) 的复杂度（采用 0-1 bfs）。

我们考虑一条 1 - a - b - c - d - 1 的路径，n^4 的枚举是不可行的。

很直接的想法是，依次考虑 a，b，c，d，发现贪心是不对的，从 1 选择了更大的权值景点 a，但是可能接下来能到达的 b 就小的可怜；而选一个权值稍小一点的 a，可能可达的 b 会很大。

那么只能考虑在枚举四元对的基础上优化。复杂度最多 \mathcal{O}(n^2)，那就只能枚举 a，b，c，d 中的两个点，剩下的两个点不能枚举，需要有一种方案快速获取最合适的点。

这个思想非常基础且常见，一种很常见的问题是低于 \mathcal{O}(n^2) 的复杂度解决二元对问题（如 P15451），或者低于 \mathcal{O}(n^3)、甚至低于 \mathcal{O}(n^2) 的复杂度解决三元对问题（如 P8667）。

此类问题的常见手段是：相比于朴素的暴力枚举二元对 / 三元对，我们只枚举二元对 / 三元对中的一元，而剩下的一元 / 二元利用预处理 / 记录前后缀最值 / 排序二分等思想，快速得到最合适的选择（如果是贪心最优化问题）；或者快速得到合法选择的数量（如果是计数问题），从而优化复杂度。

对于此题，我们要求 \mathcal{O}(n^2) 解决四元对贪心问题，那么只能枚举两元，剩余的两元必须利用手段快速得到最合适的选择。

列举这个四元对的所有限制：

然后最优化 w_a + w_b + w_c + w_d。

枚举哪两个点最合适呢？

这里可能有人问：a \ne d 难道不算 a 和 d 之间的制约吗？前面说过，互异性问题是一个比较好处理的制约，我们有比较成熟的处理手段，无需特别在意。

同时，做过一些三元对问题的同学应该有一定的直觉：三元对问题中我们也通常枚举三元对中，中间的那个元，而不是枚举落在边缘的变元。比如长度为 3 的子序列问题我们通常枚举的是这个子序列中间的那个元素。一些题目：P8667、P11794。有这个直觉的同学也更容易想到本题应当枚举中间的两个变元。

本题还有一个思考路径：思考这个题的弱化版本，如果要求的不是经过四个点，而是三个点或者两个点，应当怎么做？

根据这个思想，贪心思路比较容易想到。定义 f(u) 表示 u 可达，且和 1 可达的权值最大的景点。

这个定义是怎么来的？对着 a 和 d 的制约条件写的。容易看出，在这个定义下，合适的 a 应当取 f(b)；合适的 d 应当取 f(c)。

第一步：我们预处理出 f(u)。

第二步：直接 n^2 枚举，循环确定景点 b 和 c，要求 b 和 c 需要可达；然后记 a = f(b)，d = f(c)，试图用 w(a) + w(b) + w(c) + w(d) 更新答案，其中 w(u) 表示景点 u 的权值。

现在来解决一直被我们忽略的互异性问题。比如：会出现 f(b) = c 的情况，此时让 a = f(b) 会导致 a = c，这是不允许的。

互异性问题的解决方案通常是考虑次大值：a 应该尝试更换为 u 可达，且在家附近的权值第二大的景点。

更换定义，f(u, k) 表示 u 可达，且在家附近的权值第 k 大的景点。

当发现 f(b, 1) = c 时，将 a 设置为 f(b, 2) 即可。

当发现 f(c, 1) = b 时，将 d 设置为 f(c, 2) 即可。

发现并没有完全解决：如果这样处理后的 a 和 d 仍然重复怎么办？

还是贪心思想，考虑把 a 或者 d 换成更小的那个比较一下就行，具体来说，比如原先 a = f(b, 2)，就把 a 下调为 f(b, 3)；或者原先 d = f(c, 2)，就把 d 下调为 f(c, 3)，然后比较两种方案哪种更好就行了。

重复性解决了，但是还有个细节：如果原先 a = f(b, 1)，发现 a = d，我们想下调 a。是直接把 a 设置成 f(b, 2) 吗？错误，我们还需要检查一下 f(b, 2) 是否等于 c，如果等于 c 还需要继续下调到 f(b, 3)。下调 d 同理。

至于原先 a = f(b, 2) 为啥下调 a 不需检查？因为如果原先 a = f(b, 2) 了说明 f(b, 1) 已经等于 c 了。所以 f(b, 3) 肯定什么问题都没有。

如果直接这么写是没有问题的，但是好多细节，太麻烦。下面是一种更好写的处理方法：

直接分别枚举 a 分别作为 f(b, 1)，f(b, 2)，f(b, 3) 和 d 分别作为 f(c, 1)，f(c, 2)，f(c, 3) 组成的共九种情况，检查互异性然后更新答案即可。

需要提前预处理出 f(u, k \le 3)，其实只要在最开始 bfs 预处理的同时维护一下就行了。

细节：注意某些点可达，还与 1 可达的点数可能没有 3 个，因此注意类似访问 f(b, 3) 时产生的越界问题。

如果枚举到某个 b，c，发现 b 或者 c 有对应点数不超过 3 的情况时，这组 b，c 不一定可以生成一组合法的解，属于正常现象。题目保证全局上有解。

#include <bits/stdc++.h>
#define int long long
int read() {
    int x = 0; bool f = true; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = false;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
    return f ? x : -x;
}

const int N = 2505;
typedef std::pair<int, int> pii;
std::vector<int> G[N], f[N];
// f[u] 存放：可达 u 且可达 1 的前三大 v
bool ok[N][N]; // u 和 v 是否可达？
int n, m, k, w[N], dis[N];

void bfs(int s) {
    memset(dis, -1, sizeof(dis));
    std::queue<int> q;
    q.push(s); dis[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (u != s) {
            ok[s][u] = true;
            if (s != 1 && ok[1][u]) {
                f[s].push_back(u);
                std::sort(f[s].begin(), f[s].end(), [](int u, int v) {
                    return w[u] > w[v];
                }); // 注意这里 sort 元素数量不超过 3，效率可看作常数
            }
            if (f[s].size() > 3) f[s].pop_back();
        }
        if (dis[u] == k + 1) continue; // dis == k + 1 时已经是合法距离最远的点了，不可再向外扩展
        for (int v : G[u]) if (dis[v] == -1) {
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}

signed main() {
    n = read(); m = read(); k = read();
    for (int u = 2; u <= n; ++u) w[u] = read();
    while (m--) {
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int u = 1; u <= n; ++u) bfs(u);
    int ans = 0;
    for (int b = 2; b <= n; ++b)
        for (int c = 2; c <= n; ++c) if (ok[b][c])
            for (int a : f[b])
                for (int d : f[c])
                    if (a != c && b != d && a != d)
          // b != c 由 ok[b][c] 的定义保证；a != b，c != d 由 f 的定义保证
                        ans = std::max(ans, w[a] + w[b] + w[c] + w[d]);
    printf("%lld\n", ans);
    return 0;
}

如果觉得这篇题解写得好，请不要忘记点赞，谢谢！