「USACO 2022.12 Platinum」Breakdown 题解

题目大意

给定一个 $N$ 个节点的带权有向完全图（包括自环），需要按顺序删除 $N^2$ 条边。在每次删除后，求从节点 $1$ 到节点 $N$ 的恰好经过 $K$ 条边的路径的最小权值和。如果不存在这样的路径，输出 $-1$。

解题思路

关键观察

1. 反向处理：从空图开始，逆序添加边，这样每次只需要考虑新边带来的更新
2. 分层图模型：将问题转化为在分层图中求最短路
3. 状态定义：用 $id[i][j]$ 表示「到达节点 $i$ 且已经走了 $j$ 条边」这个状态

算法核心

状态设计

• 定义状态 $(i, j)$：当前在节点 $i$，已经走了 $j$ 条边
• 状态总数：$N \times (K+1)$
• 初始状态：$(1, 0)$，距离为 $0$
• 目标状态：$(N, K)$

边添加与更新

当添加边 $(u, v)$ 时：

• 对于所有 $j \in [0, K-1]$，可以从状态 $(u, j)$ 转移到状态 $(v, j+1)$
• 转移代价为 $w[u][v]$

最短路算法

使用 SPFA（队列优化的Bellman-Ford）进行动态更新：

• 每次添加边后，从新边出发进行松弛操作
• 由于 $K$ 很小（$K \leq 8$），状态数有限，SPFA 效率可以接受

代码解析

#include <bits/stdc++.h>
#define ci const int
using namespace std;

ci N = 305, K = 9, M = N * K, inf = 1e9;
int n, k, cnt, ans[N * N], dis[M], id[N][K], w[N][N], dx[N * N], dy[N * N];
bool in[M];
vector<pair<int, int>> g[M];  // 邻接表：g[u] = {(v, w)}
queue<int> q;

// 松弛操作
void upd(ci x, ci d) {
    if (d < dis[x]) {
        dis[x] = d;
        if (!in[x]) q.push(x), in[x] = 1;
    }
}

int main() {
    scanf("%d%d", &n, &k);
    
    // 读入边权
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &w[i][j]);
    
    // 状态编号
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            id[i][j] = ++cnt;
    
    // 读入删除顺序（逆序使用）
    for (int i = 1; i <= n * n; ++i)
        scanf("%d%d", &dx[i], &dy[i]);
    
    // 初始化距离
    for (int i = 1; i <= cnt; ++i) dis[i] = inf;
    dis[id[1][0]] = 0;
    
    // 逆序处理：从空图开始，逐步加边
    for (int i = n * n; i; --i) {
        // 记录当前答案
        ans[i] = (dis[id[n][k]] == inf) ? -1 : dis[id[n][k]];
        
        // 添加边 (dx[i], dy[i])
        for (int j = 0; j < k; ++j) {
            int u = id[dx[i]][j], v = id[dy[i]][j + 1];
            g[u].push_back({v, w[dx[i]][dy[i]]});
            upd(v, dis[u] + w[dx[i]][dy[i]]);
        }
        
        // SPFA 更新
        while (!q.empty()) {
            ci x = q.front(); q.pop();
            in[x] = 0;
            for (auto tmp : g[x])
                upd(tmp.first, dis[x] + tmp.second);
        }
    }
    
    // 输出答案（正序）
    for (int i = 1; i <= n * n; ++i)
        printf("%d\n", ans[i]);
    
    return 0;
}

复杂度分析

• 状态数：$O(N \times K)$，其中 $N \leq 300$，$K \leq 8$
• 边数：每次添加一条边，会创建 $K$ 条新边
• 总复杂度：$O(N^2 \times K \times (N \times K))$，在题目约束下可接受

样例解释

对于样例：

3 4
10 4 4
9 5 3  
2 1 6
...

• 初始时（删除所有边后）：没有路径，输出 $-1$
• 逐步添加边，路径逐渐出现：
  • 第 $6$ 次删除后：出现路径 $1 \to 3 \to 3 \to 3 \to 3$，权值 $22$
  • 第 $2$ 次删除后：出现更优路径 $1 \to 3 \to 2 \to 1 \to 3$，权值 $18$
  • 第 $1$ 次删除后：出现最优路径 $1 \to 2 \to 3 \to 2 \to 3$，权值 $11$

总结

本题的巧妙之处在于：

1. 逆序处理：将删除问题转化为添加问题
2. 分层图建模：将「恰好 $K$ 步」的条件转化为图的结构
3. 动态更新：利用 SPFA 的特性进行增量更新

这种「反向处理 + 分层图」的思路在解决动态图问题中非常有效。