P8817

· · 题解

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

下文中，

注意，为方便，特殊地，我们认为自己和自己不可达。

观察数据范围，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 会很大。

但有一种贪心是对的，那就是确定了 a，b，c，选择 d 的时候。如果我们确定了 c，那么直接选择 c 可达的，在家附近的，不为 a 也不为 b 的权值最大的景点作为 d 即可。反正 d 之后没有景点了，所以可以直接贪心，没有后顾之忧。

由于环的对称性，可以发现确定了 b，c，d 之后，也可以贪心地选择 a。

有了大体思路。

我们定义 f(u) 表示 u 可达，且在家附近的权值最大的景点。

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

第二步：直接 n^2 枚举，循环确定景点 b 和 c（b \ne 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 预处理的同时维护一下就行了。

注意某些点可达，还在家附近的点数可能没有 3 个，因此注意类似访问 f(b, 3) 时产生的越界问题。

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

题目保证全局上是有解的。

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2022-10-30 17:40:03 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2022-10-30 19:07:52
 */

#include <bits/stdc++.h>
#define int long long
inline int read() {
    int x = 0;
    bool flag = true;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            flag = false;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    if(flag)
        return x;
    return ~(x - 1);
}

const int maxn = 2505;
typedef std :: pair <int, int> pii;

std :: vector <int> G[maxn];
int w[maxn];
bool ok[maxn][maxn]; // u, v 是否可达
std :: vector <int> f[maxn]; // f[u] 存放：可达 u 且可达 1 的前三大 v

int k;

int dis[maxn];

void bfs(int x) {
    std :: memset(dis, -1, sizeof(dis));
    std :: queue <int> q;
    q.push(x);
    dis[x] = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (u != x) {
            ok[x][u] = true;
            if (x != 1 && ok[1][u]) {
                // printf("%lld %lld\n", x, u);
                f[x].push_back(u);
                std :: sort(f[x].begin(), f[x].end(), [](int u, int v) {
                    return w[u] > w[v];
                }); // 注意这里 sort 元素数量不超过 3，效率可看做常数
                if (f[x].size() > 3)
                    f[x].pop_back();
            }
        }

        if (dis[u] == k + 1)
            continue;

        for (int v : G[u]) if (dis[v] == -1) {
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
}

inline bool gmx(int &a, int b) {
    return b > a ? a = b, true : false;
}

signed main() {
    int 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)
                    // 其他不等关系天然满足了，只有这三组需要检验；
                    // 天然满足的不等关系：a != b，b != c，c != d，请读者自己思考为什么。
                        gmx(ans, w[a] + w[b] + w[c] + w[d]);

    printf("%lld\n", ans);
    return 0;
}

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