「CSP-S 2022」假期计划 题解

算法思路

本题使用BFS预处理和贪心枚举来解决带约束的路径优化问题。核心思想是通过BFS预处理所有可达点对，然后枚举中间两个景点，利用预处理的候选集来快速找到最优解。

关键观察

1. 路径结构分析

行程结构为：$1 \to A \to B \to C \to D \to 1$

• 每段行程转车不超过 $k$ 次
• $A,B,C,D$ 是四个不同的景点
• 需要最大化四个景点的分数和

2. 预处理优化

对于每个景点 $x$，预处理从家 ($1$) 和从 $x$ 出发在 $k+1$ 步内能到达的点，并保留分数最大的前 $3$ 个候选点。

代码解析

数据结构定义

const int N = 2550;
int val[N], n, m, k, ans = -INF;
bool b[N][N];        // 可达性矩阵
vector<int> g[N];    // 邻接表
vector<int> cho[N];  // 每个点的候选前驱（分数最大的前3个）

BFS预处理

void bfs(int x) {
    int dis[N];
    memset(dis, INF, sizeof dis);
    dis[x] = 0;
    queue<int> q;
    q.push(x);
    
    while (q.size()) {
        int t = q.front(); q.pop();
        
        if (x != t) {
            b[x][t] = 1;  // 标记可达
            
            // 如果从家能到达t，且当前不是家，则加入候选
            if (x != 1 && b[1][t]) {
                cho[x].push_back(t);
                sort(cho[x].begin(), cho[x].end(), cmp);
                if (cho[x].size() > 3) {
                    cho[x].pop_back();  // 只保留前3个
                }
            }
        }
        
        if (dis[t] > k) continue;
        
        for (auto i : g[t]) {
            if (dis[i] > dis[t] + 1) {
                dis[i] = dis[t] + 1;
                q.push(i);
            }
        }
    }
}

主枚举逻辑

for (int B = 2; B <= n; B++) {
    for (int C = 2; C <= n; C++) {
        if (B != C && b[B][C]) {  // B和C之间可达
            for (auto A : cho[B]) {  // A是B的候选前驱
                for (auto D : cho[C]) {  // D是C的候选后继
                    if (dif(A, B, C, D)) {  // 四个点互不相同
                        ans = max(ans, val[A] + val[B] + val[C] + val[D]);
                    }
                }
            }
        }
    }
}

算法正确性

可达性保证

• 通过BFS计算最短路径，确保每段行程转车不超过 $k$ 次
• 预处理时检查 $b[1][t]$ 确保从家可达

候选集优化正确性

• 每个点只保留分数最大的前 $3$ 个候选点
• 数学上可以证明，最优解中的 $A$ 和 $D$ 一定在对应的候选集中

完整性检查

bool dif(int A, int B, int C, int D) {
    return A != C && B != D && A != D;
}

确保四个景点互不相同

复杂度分析

• BFS预处理：$O(n(n+m))$，每个点做一次BFS
• 枚举过程：$O(n^2 \times 9)$，每个 $(B,C)$ 对枚举 $3 \times 3$ 种组合
• 总复杂度：$O(n^2 + nm)$，满足 $n \leq 2500$ 的约束

关键技巧

1. BFS预处理：快速计算所有点对之间的可达性
2. 候选集剪枝：每个点只保留前 $3$ 个最优候选，将指数枚举降为常数
3. 可达性矩阵：$O(1)$ 查询两点是否在 $k+1$ 步内可达
4. 对称性利用：$A$ 和 $D$ 都通过候选集预处理，减少枚举量