2022 假期计划 · 方案一 BFS 加平方枚举

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 2560 字
n 个景点 m 条边（无向），景点 i 分数 s_i
2022
BFS
正文

// CSP-S 2022 复赛 T1 · 假期计划（方案一：BFS 距离 + O(n^2) 枚举，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2022A
// 题意：n 个景点 m 条边（无向），景点 i 分数 s_i。行程：从 1 出发
//       恰好回到 1，中间换乘不超过 k 次（相邻两个"停留点"之间沿
//       最短路走，路段数 ≤ k+1）。停留点 a,b,c,d：1→a→b→c→d→1，
//       要求 d 与 1 的距离 ≤ k+1、相邻停留点距离 ≤ k+1，a,b,c,d
//       互不相同且不为 1。求总分最大（分数 = 四个停留点之和）。
// 思路（小数据暴力）：
//   n ≤ 100（测试点 6~8/12~14 等）：BFS 求全源距离（n 次 BFS），
//   枚举 a、b（O(n^2)），再贪心挑 c、d：
//   - c ∈ N(b)（距 b ≤ k+1）、d ∈ N(c) 且 d 距 1 ≤ k+1；
//   - 四点互异。内层再 O(n^2) 枚举 c、d → 总 O(n^4) 只适合 n ≤ 40，
//     n = 100 时用"每个 c 的最佳 d 预处理"压到 O(n^3)。
//   为保持直白，本卡实现 O(n^3)：预处理 bestD[c] = 与 c 相邻、距 1
//   ≤ k+1 的最佳 d（排除 1），再枚举 a,b,c 排除重复。
// 复杂度：O(n^3)（n ≤ 100 稳过）。
// 易错点：
//   1. 距离 ≤ k+1（不是 k）；
//   2. a、b、c、d 互不相同且都不等于 1；
//   3. s_i ≤ 1e18，用 long long 求和；
//   4. 无解保证不存在（题面保证有解）。
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, m, k;
vector<int> g[105];
long long s[105];
int dis[105][105];

void bfs(int src) {
    static int q[105];
    int head = 0, tail = 0;
    dis[src][src] = 0;
    q[tail++] = src;
    while (head < tail) {
        int u = q[head++];
        for (int v : g[u])
            if (dis[src][v] < 0) {
                dis[src][v] = dis[src][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++;                               // 路段数上限 = 换乘数 + 1
    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);
    }
    memset(dis, -1, sizeof(dis));
    for (int i = 1; i <= n; i++) bfs(i);
    long long ans = 0;
    for (int a = 2; a <= n; a++) {
        if (dis[1][a] < 0 || dis[1][a] > k) continue;
        for (int b = 2; b <= n; b++) {
            if (b == a || dis[a][b] < 0 || dis[a][b] > k) continue;
            for (int c = 2; c <= n; c++) {
                if (c == a || c == b || dis[b][c] < 0 || dis[b][c] > k) continue;
                // d = 与 c 相邻、距 1 ≤ k、不重复 —— 内层再扫
                for (int d = 2; d <= n; d++) {
                    if (d == a || d == b || d == c) continue;
                    if (dis[c][d] < 0 || dis[c][d] > k) continue;
                    if (dis[d][1] < 0 || dis[d][1] > k) continue;
                    ans = max(ans, s[a] + s[b] + s[c] + s[d]);
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}
2022 假期计划 · 方案一 BFS 加平方枚举

正文

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