UVa 12717 Fiasco

题目描述

$\text{Natasha}$ 在算法课上总是混淆概念。上周，$\text{Chhaya Murthy}$ 教授布置了一个经典问题：在加权图中从指定源点出发计算到所有节点的最短路径。而在此之前，教授讲授了 $\text{Prim}$ 算法和 $\text{Dijkstra}$ 算法，它们看起来相似但功能截然不同。$\text{Natasha}$ 被搞糊涂了，她提交了一个与 $\text{Prim}$ 算法非常相似的代码（我们称之为 $\text{Natasha}$ 算法），并且没有充分测试。她的伪代码如下：

function Shortest(Graph, source):
for each vertex v in Graph:
visited[v] := false;
dist[v] := infinity;
previous[v] := undefined;
ans[v] := undefined;
end for
dist[source] := 0;
Q := {} // priority queue, pop gives node with smallest dist, tie by smallest id
Push (source, dist[source]) to Q
while Q is not empty:
Pop node u from Q;
visited[u] := true;
if dist[u] == infinity: break;
for each neighbor v of u:
if visited[v] == true: continue;
alt := edge_cost(u, v);
if alt < dist[v]:
dist[v] := alt;
previous[v] := u;
Push (v, dist[v]) to Q;
end for
end while
for each node node in Graph:
answer := 0;
u := node;
while previous[u] is defined:
answer := answer + edge_cost(u, previous[u]);
u := previous[u];
end while
ans[node] := answer;
return ans;
endfunction

提交后，她的朋友发现了漏洞。为了帮助她，$\text{Rehan}$ 要求她不要改变边连接的顶点，也不要改变边权重的整体集合，她只能重新排列哪些权重分配给哪些边。请帮助她找到一种边权重分配方案，使得 $\text{Natasha}$ 的算法在重新分配后的图上能够正确输出从源点到所有节点的最短路径。

输入格式

第一行包含测试用例数 $T$（$1\le T\le 15$）。
每个测试用例的第一行包含三个整数 $n,m,source$（$2\le n\le 2500$，$1\le m\le 25000$，$1\le source\le n$），分别表示节点数、边数和源点编号。
接下来 $m$ 行，每行三个整数 $u,v,w$，表示节点 $u$ 和 $v$ 之间有一条权重为 $w$ 的边（$1\le w\le m$）。
保证图中没有重边或自环，图是连通的，且所有边的权重互不相同。

输出格式

对于每个测试用例，首先输出一行 Case X，其中 $X$ 是测试用例编号。
然后按输入顺序输出每条边的三个整数 $u,v,w$，每个三元组占一行，用空格分隔。
如果有多个可行解，输出任意一个。

样例

输入

1
7 9 5
2 4 2
1 4 8
7 2 6
3 4 7
5 7 5
7 3 9
6 1 1
6 3 4
5 6 3

输出

Case 1:
2 4 7
1 4 8
7 2 3
3 4 9
5 7 1
7 3 4
6 1 5
6 3 6
5 6 2

题目分析

$\text{Natasha}$ 的算法本质上就是 $\text{Prim}$ 算法：它维护一个已访问集合，每次从优先队列中取出 dist 最小的节点，然后对于未访问的邻居，如果边权小于当前记录的 dist，则更新 dist 为边权，并记录前驱。注意，这里的 dist 并不是从源点到该节点的累计距离，而仅仅是连接边的最小权值，因此它实际上是在构建一棵最小生成树（从源点出发的 $\text{Prim}$ 树）。

题目要求重新分配边权（使用给定的权重集合 $\{1,2,\dots ,m\}$），使得在这组新权重下，$\text{Natasha}$ 算法最终输出的 ans（沿前驱累加边权）恰好等于从源点到每个节点的真实最短路径（同样在新权重下）。

也就是说，我们需要构造一组边权排列，使得 $\text{Prim}$ 算法选出的边恰好构成一棵最短路径树（$\text{SPT}$）。

解题思路

关键观察

• $\text{Prim}$ 算法在选择边时，总是选择当前已访问集合到未访问集合的最小权边。
• 如果我们能够控制权重的分配，使得 $\text{Prim}$ 在扩展时严格按照某种层次顺序进行，那么它就能生成一棵特定的树。
• 最短路径树的一个自然候选是从源点出发的 $\text{BFS}$ 树，因为它保证了从源点到每个节点的跳数最少。但仅凭跳数少并不足以保证路径总权值最小，我们需要进一步设计权值，使得 $\text{BFS}$ 树路径的总权值严格小于任何经过非树边的路径。

构造方法

我们可以利用 $\text{BFS}$ 的顺序来分配权重，具体步骤如下：

为什么这样构造是可行的？

• $\text{BFS}$ 保证了节点按离源点的跳数（深度）递增的顺序被访问。因此，连接深度 $d$ 和 $d+1$ 的边会在连接深度 $d+1$ 和 $d+2$ 的边之前被分配权重。
• 由于所有权重都是按发现顺序递增的，$\text{Prim}$ 算法在从源点开始扩展时，会优先选择这些被早期分配的边。实际上，$\text{Prim}$ 的扩展顺序将完全与 $\text{BFS}$ 的层次顺序一致，最终生成的就是这棵 $\text{BFS}$ 树。
• 对于任意一个深度为 $d$ 的节点，从源点到它的 $\text{BFS}$ 树路径恰好包含 $d$ 条边，且这些边的权重依次为 $1,2,\dots ,d$（因为它们是 $\text{BFS}$ 过程中最先被分配的 $d$ 条边），路径总权值为 $1+2+\cdots +d=\frac{d(d+1)}{2}$。
• 任何包含非树边的路径，其第一条非树边一定是在 $\text{BFS}$ 中较晚被发现（即权重较大）的边，它的权值至少为 $d+1$。而整条路径的总权值必然大于等于这条非树边的权值，因此必然大于 $\frac{d(d+1)}{2}$（当 $d\ge 1$ 时，$\frac{d(d+1)}{2}>d$，且 $d+1>d$，但更严格地，$\frac{d(d+1)}{2}$ 对于 $d\ge 2$ 已经大于 $d+1$，对于 $d=1$，树路径权值为 $1$，而非树边最小为 $2$，也满足）。所以树路径是严格最短的。

因此，这种分配方案能够保证 $\text{BFS}$ 树就是新权重下的最短路径树，从而 $\text{Natasha}$ 算法（即 $\text{Prim}$）会选中这些树边，并最终输出正确的最短距离。

算法步骤

复杂度分析

• $\text{BFS}$ 遍历所有节点和边，时间复杂度为 $O(n+m)$。
• 使用邻接矩阵（$n\le 2500$）时，每次检查所有邻居需要 $O(n^2)$，但 $n$ 较小，可以接受。也可以使用邻接表优化到 $O(n+m)$。
• 空间复杂度 $O(n^2)$（邻接矩阵）或 $O(n+m)$（邻接表）。

代码实现

// Fiasco
// UVa ID: 12717
// Verdict: Accepted
// Submission Date: 2026-06-24
// UVa Run Time: 0.070s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const int MAXN = 2505;
int n, m, source;
int g[MAXN][MAXN]; // 存储分配后的边权，-1 表示无边
int origU[25005], origV[25005]; // 保存输入顺序的端点
bool visited[MAXN][MAXN]; // 标记边是否已在 BFS 中被分配

void bfs() {
queue<int> q;
int weight = 1;
q.push(source);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v = 1; v <= n; ++v) {
if (g[u][v] != –1 && !visited[u][v]) {
// 边 (u,v) 第一次被发现，分配权重
g[u][v] = g[v][u] = weight++;
visited[u][v] = visited[v][u] = true;
q.push(v);
}
}
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
for (int cs = 1; cs <= T; ++cs) {
cin >> n >> m >> source;

// 初始化邻接矩阵
memset(g, –1, sizeof(g));
memset(visited, false, sizeof(visited));

for (int i = 0; i < m; ++i) {
int w;
cin >> origU[i] >> origV[i] >> w;
// 仅标记存在边，权重暂存为 0（后续被覆盖）
g[origU[i]][origV[i]] = g[origV[i]][origU[i]] = 0;
}

bfs();

cout << "Case " << cs << ":\\n";
for (int i = 0; i < m; ++i)
cout << origU[i] << ' ' << origV[i] << ' ' << g[origU[i]][origV[i]] << '\\n';
}
return 0;
}

总结

本题的关键在于将 $\text{Prim}$ 算法的行为引导到构造最短路径树的目标上。通过 $\text{BFS}$ 顺序分配边权，我们可以让 $\text{Prim}$ 按照 $\text{BFS}$ 的层次扩展，并利用权重递增的特点保证 $\text{BFS}$ 树路径的总权值小于任何包含非树边的路径。这种构造方法巧妙地将图论中的 $\text{BFS}$ 与 $\text{Prim}$ 算法联系起来，避免了复杂的贪心证明，是解决此类“重排边权使错误算法变正确”问题的经典技巧。

核心要点：

• 利用 $\text{BFS}$ 天然的分层特性控制边的优先级。
• 权重递增使树路径的权值和与深度挂钩，确保最短性。
• 代码实现简洁，时间复杂度低，适合题目给定的数据范围。