2022 假期计划 · 方案二预处理最佳中转

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 2838 字
预处理每个点的最佳中转，RMQ 上 O(n^2) 转移
2022
BFS
正文

// CSP-S 2022 复赛 T1 · 假期计划（方案二：预处理最佳中转 + O(n^2)，满分）
// 原题：https://oj.yecheng.tv/p/CSPS2022A
// 题意：同方案一（n ≤ 2500，m ≤ 1e4，需满分）。
// 思路（把 c、d 打包预处理）：
//   枚举 a、b 后，需要"与 b 距离 ≤ k 的 c"接"与 c 相邻且距 1 ≤ k 的
//   最佳 d"。d 与 1 相邻（k≥1 时 d ∈ N(1)）——枚举 d ∈ N(1)，其邻点
//   c 贡献 s_c + s_d 给所有 b ∈ N(c)（b ∉ {1, d}）：预处理
//       f[b] = max{ s_c + s_d }（c-d 相邻、d ∈ N(1)、b ∈ N(c)），
//   并为每个 b 存前几优候选（候选的 c、d 需排除 a）→ 每个候选记录
//   (值, c, d)，按值降序取前 3 个即可在枚举 a 时跳过冲突。
//   然后 a ∈ N_k(1)（dis(1,a) ≤ k）、b ∈ N_k(a)（dis(a,b) ≤ k），
//   排除 a、b 与 1，答案 = max s_a + s_b + f[b]（跳过含 a 的候选）。
// 复杂度：O(Σ deg^2 + n^2)。
// 易错点：
//   1. f[b] 的候选必须排除 1 与 b，且枚举 a 时再排除 a；
//   2. 距离 ≤ k+1（k 先自增）；
//   3. 存前 3 优是因为 a、b、c、d 四点互斥最多排掉两个候选；
//   4. long long 全程。
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, k;
vector<int> g[2505];
long long s[2505];
int dis1[2505], disa[2505];

struct Cand {
    long long v;
    int c, d;
};
vector<Cand> f[2505];

void bfs(int src, int* dis) {
    static int q[2505];
    int head = 0, tail = 0;
    for (int i = 1; i <= n; i++) dis[i] = -1;
    dis[src] = 0;
    q[tail++] = src;
    while (head < tail) {
        int u = q[head++];
        for (int v : g[u])
            if (dis[v] < 0) {
                dis[v] = dis[u] + 1;
                q[tail++] = v;
            }
    }
}

int main() {
    freopen("holiday.in", "r", stdin);
    freopen("holiday.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    k++;
    for (int i = 2; i <= n; i++) scanf("%lld", &s[i]);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // 预处理 f[b]：枚举 d ∈ N(1)（d≠1），c ∈ N(d)（c≠1,d），
    // 贡献给 b ∈ N(c)（b≠1,d,c）
    for (int d : g[1]) {
        if (d == 1) continue;
        for (int c : g[d]) {
            if (c == 1 || c == d) continue;
            for (int b : g[c]) {
                if (b == 1 || b == c || b == d) continue;
                f[b].push_back({s[c] + s[d], c, d});
            }
        }
    }
    for (int b = 2; b <= n; b++) {
        sort(f[b].begin(), f[b].end(), [](const Cand& x, const Cand& y) {
            return x.v > y.v;
        });
        if (f[b].size() > 3) f[b].resize(3);
    }
    bfs(1, dis1);
    long long ans = 0;
    for (int a = 2; a <= n; a++) {
        if (dis1[a] < 0 || dis1[a] > k) continue;
        bfs(a, disa);
        for (int b = 2; b <= n; b++) {
            if (b == a || disa[b] < 0 || disa[b] > k) continue;
            for (const Cand& cd : f[b]) {
                if (cd.c == a || cd.d == a) continue;
                long long tot = s[a] + s[b] + cd.v;
                if (tot > ans) ans = tot;
                break;                 // 已按值降序，第一个可行即最优
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}
2022 假期计划 · 方案二 预处理最佳中转

正文

CSP-S 标程 · 复赛真题的其它内容

2022 假期计划 · 方案二预处理最佳中转
