P8817 CSP-S 2022 假期计划 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
下文中，\(u \to v\) 可达意为 \(u \to v\) 可以经过不多于 \(k\) 次转车到达，即 \(u\) 到 \(v\) 的距离不多于 \(k + 1\)。
注意，为方便，我们认为自己和自己不可达。
观察数据范围，\(n^2\) 可过，已经足够处理出每个点对之间的距离了。因此首先应该 \(n^2\) 计算任意点对之间是否可达。
然后比较难搞的部分就在于不能走重复节点，因此 dp 存在困难。
我们考虑一条 \(1 \to a \to b \to c \to d \to 1\) 的路径，\(n^4\) 的枚举是不可行的，但是我们能发现，如果我们先允许 \(a = d\)，那么：
如果 \(b\) 是确定的，那么 \(a\) 一定是满足：与 \(1\)、与 \(b\) 均可达的，不为 \(c\) 的，权值最大的那个节点；
如果 \(c\) 是确定的，那么 \(d\) 一定是满足：与 \(1\)、与 \(c\) 均可达的，不为 \(b\) 的，权值最大的那个节点。
初步考虑：提前预处理出每个节点 \(u\) 对应的权值最大的节点 \(v\)，使得 \(v\) 和 \(u\)，\(v\) 和 \(1\) 之间均可达。\(n^2\) 枚举 \(b, c\) 即可。
但是如果点 \(b\) 计算出来对应权值最大的节点是 \(c\) 怎么办？
所以我们应该计算 \(b\) 对应的权值前两大的节点 \(v1, v2\)，对应权值分别为 \(w1, w2\)，其中 \(w1 \ge w2\)。我们优先考虑使用 \(v1\) 当做 \(a\)，如果发现 \(v1 = c\)，那么再把 \(v2\) 当做 \(a\) 就可以了。
\(c\) 计算出权值最大节点是 \(b\) 这种情况也是同样的处理方式。
根据这样的处理思想，就不难考虑出不允许 \(a=d\) 怎样做了。
假设 \(b\) 对应的前两大节点是 \(v1, v2\)，\(c\) 对应的前两大节点是 \(v4, v5\)。我们先分别计算出 \(a\) 和 \(d\)。
如果 \(a = d\)，那么我们有两种方向，一是把 \(a\) 换成 \(b\) 对应权值更小的那个，二是把 \(d\) 换成 \(c\) 对应权值最小的那个。
如果 \(a\) 已经是 \(v2\) 了，换成下一个权值最小的应该是 \(v3\)。所以我们应该记录每个节点对应的前三大。
但是有一个细节，如果 \(a\) 已经是 \(v1\)，\(a = d\) 时，换成权值最小的那个是 \(v2\) 吗？不一定，因为 \(v2\) 可能等于 \(c\)，此时 \(a\) 是 \(v3\)。提供一组关于这方面的 hack 数据。
为了避免这样的麻烦，我们把 \(a\)，\(b\) 分别等于 \(v1, v2,v3\)，\(v4, v5, v6\) 的九种情况全部排列，检验重复性并取最大值即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
我个人是不太会大佬的一些“显然”，“易得”，“观察到”之类的高端操作的，这里给大家讲一下我是怎么想到这个思路的。
先考虑 \(b\) 和 \(c\)，再考虑 \(a\) 和 \(d\) 是怎么想到的？
我一开始也是依次考虑的 \(a, b, c, d\)。发现贪心是不对的，从 \(1\) 选择了更大的权值 \(a\)，但是可能接下来的 \(b\) 就小的可怜。
但是有一种贪心是对的，那就是选择 \(d\) 的时候。如果我们确定了 \(c\)，那么直接选择和 \(c\)，和 \(1\) 都可达的那个没重复过的最大权值节点是肯定没问题的，反正 \(d\) 之后就回到 \(1\) 了，没有后顾之忧。
然后这个路径，它其实是有对称性的，确定了 \(c\)，能贪心地选择 \(d\)，那确定了 \(b\)，也可以贪心地选择 \(a\)。
那确定 \(b\) 和 \(c\)？只需要 \(n^2\) 的复杂度。而贪心地选最大，似乎可以直接预处理。
然而发现只保留第一大会造成景点重复性的一些问题。\(b\) 既可以和 \(c\) 重复，还可以和 \(d\) 重复，因此应该记录前三大，这样就没问题了。
另外，个人认为本题并不像流传的那样简单，所以没做上这题的同学不必太抑郁。
/*
* @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)
// 其他不等关系一定是满足的，只有这三组需要检验
gmx(ans, w[a] + w[b] + w[c] + w[d]);
printf("%lld\n", ans);
return 0;
}
如果觉得这篇题解写得好，请不要忘记点赞，谢谢！
标签：P8817,int,CSP,v2,maxn,2022,权值,节点,dis From： https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p8817.html