【广度优先搜索，枚举】假期计划

题意概括

给定一张 $N$ 个点、$M$ 条边的无向连通图，点 1 代表家。需要挑选 4 个互不相同的景点，依次记为 A、B、C、D。要求在 $1 \to A \to B \to C \to D \to 1$ 的 5 段行程中，每段行程经过的最短边数不能超过 $K+1$。每个景点都有一个固定的分数，求 A、B、C、D 四个景点的分数之和的最大值。 输入包含三个整数 $N, M, K$，各个景点的分数，以及连边的具体信息。其中 $5 \le N \le 2500$，$1 \le M \le 10000$。

样例分析

输入样例： 8 8 1 9 7 1 8 2 3 6 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 1

以点 1 为家，每段行程转车不超过 1 次，也就是单次最多跨越 2 条边。 从图的连通情况看，距离点 1 步数在 2 以内的候选点有 2、3、8、7。 如果依次挑选 2、3、5、7 作为行程节点，各段相邻点的图上最短距离均不超过 2，且节点互不相同。它们的分数分别是 9、7、8、3，求和得到 27。穷举验证可知无法找到总分更高的合法组合。

题目分析

看到 $N \le 2500$ 这个条件。如果老老实实写四重循环去枚举 A、B、C、D，时间复杂度高达 $O(N^4)$，哪怕剪枝再精细也会超时。要稳过这道题，必须把枚举压到两层循环，也就是 $O(N^2)$ 的级别。

要把 4 个变量的枚举变成 2 个，突破口在路径的结构上。 我们要走的路径是 $1 \to A \to B \to C \to D \to 1$。它是一个首尾相接的对称环。如果在中间切一刀，把 $B$ 和 $C$ 当作桥墩确定下来，整个过程就被劈成了左半边 $1 \to A \to B$ 和右半边 $C \to D \to 1$。 一旦 $B$ 被外层循环固定，给它找前驱 $A$ 的任务只和 $B$ 与 1 有关；一旦 $C$ 固定，找后继 $D$ 的任务只和 $C$ 与 1 有关。这两半是解耦的，把它们拆开分别处理，这就是折半枚举的核心动机。

于是思路变成了：双重循环枚举 $B$ 和 $C$。对于每一个可能作为桥墩的节点，提前帮它把所有能作为 $A$ 或者 $D$ 的候选点找出来。 为了让总分最大，预处理时可以直接挑分数最大的那个候选点吗？ 题目规定 4 个点必须互不相同，直接贪心选最大的容易翻车。假设预处理时只给每个点记录了分数第一的候选点，当外层循环枚举到具体的 $B$ 和 $C$ 时，万一 $B$ 记录的那个最强 $A$ 恰好就是 $C$，或者恰好和 $D$ 撞了位置，唯一的备选就失效了，这条路直接作废。

算一下具体的排斥情况：给 $B$ 找 $A$ 的时候，$A$ 需要避让的“竞争者”最多只有三个，分别是当前的 $B$、当前的 $C$、以及 $C$ 选出来的 $D$。 在最极端的冲突下，分数第一大的备选被 $C$ 占了，第二大的备选被 $D$ 占了，那么第三大的备选就一定是个自由身。也就是说，在预处理阶段，只要把满足连通条件的备选点按分数从大到小排个序，只存前 3 个，就足以应付所有位置重合的极端情况。 通过维护前 3 大这个常数级的操作，既完美避开了去重的雷区，又不需要增加多余的循环层数，将复杂度彻底锁在了 $O(N^2)$。

参考实现

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, k;
ll val[2505];
vector<int> g[2505];
int ok[2505][2505];
int dis[2505];
int bst[2505][5];

void bfs(int s) {
    for (int i = 1; i <= n; ++i) {
        dis[i] = -1;
    }
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dis[u] == k + 1) continue;
        for (int v : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (dis[i] != -1 && dis[i] <= k + 1) {
            ok[s][i] = 1;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> m >> k;
    for (int i = 2; i <= n; ++i) {
        cin >> val[i];
    }
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    for (int i = 1; i <= n; ++i) {
        bfs(i);
    }
    
    for (int i = 2; i <= n; ++i) {
        vector<int> tmp;
        for (int j = 2; j <= n; ++j) {
            if (i != j && ok[1][j] && ok[j][i]) {
                tmp.push_back(j);
            }
        }
        sort(tmp.begin(), tmp.end(), [&](int x, int y) {
            return val[x] > val[y];
        });
        int sz = tmp.size();
        for (int j = 0; j < 3 && j < sz; ++j) {
            bst[i][j] = tmp[j];
        }
    }
    
    ll ans = 0;
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= n; ++j) {
            if (i == j || !ok[i][j]) continue;
            for (int x = 0; x < 3; ++x) {
                int a = bst[i][x];
                if (!a || a == j) continue;
                for (int y = 0; y < 3; ++y) {
                    int d = bst[j][y];
                    if (!d || d == i || d == a) continue;
                    ans = max(ans, val[a] + val[i] + val[j] + val[d]);
                }
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度：单次广度优先搜索求全源短路耗时 $O(N+M)$，执行 $N$ 次耗时 $O(N(N+M))$。对于每个节点寻找备选集合并排序，单次耗时 $O(N \log N)$，整理所有节点耗时 $O(N^2 \log N)$。核心的两重循环加内层最多 9 次的组合检测耗时 $O(N^2)$。综合时间复杂度为 $O(N(N+M) + N^2 \log N)$。 空间复杂度：存储全图连通关系的二维矩阵占用 $O(N^2)$。邻接表占用 $O(N+M)$，备选数组占用常数倍的 $O(N)$。整体空间复杂度为 $O(N^2)$。

https://www.luogu.com.cn/problem/P8817