企业官网建设流程全解析

题目描述

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

functionShortest(Graph,source):foreach vertex v in Graph:visited[v]:=false;dist[v]:=infinity;previous[v]:=undefined;ans[v]:=undefined;endfordist[source]:=0;Q:={}// priority queue, pop gives node with smallest dist, tie by smallest idPush(source,dist[source])to QwhileQ isnotempty:Pop node u from Q;visited[u]:=true;ifdist[u]==infinity:break;foreach neighbor v of u:ifvisited[v]==true:continue;alt:=edge_cost(u,v);ifalt<dist[v]:dist[v]:=alt;previous[v]:=u;Push(v,dist[v])to Q;endforendwhileforeach node node in Graph:answer:=0;u:=node;whileprevious[u]is defined:answer:=answer+edge_cost(u,previous[u]);u:=previous[u];endwhileans[node]:=answer;returnans;endfunction

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

输入格式

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

输出格式

对于每个测试用例，首先输出一行Case X，其中XXX是测试用例编号。
然后按输入顺序输出每条边的三个整数u,v,wu, v, wu,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

题目分析

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

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

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

解题思路

关键观察

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

构造方法

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

1. 从源点sourcesourcesource开始进行BFS\texttt{BFS}BFS，遍历整个图。
2. 在BFS\texttt{BFS}BFS过程中，每当从当前节点uuu第一次访问到一条连接未访问节点vvv的边(u,v)(u,v)(u,v)时，就给这条边分配当前最小的未使用权重（从111开始递增）。
3. 这样，BFS\texttt{BFS}BFS先发现的边获得较小的权重，后发现的边获得较大的权重。

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

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

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

算法步骤

1. 读取n,m,sourcen, m, sourcen,m,source。
2. 使用邻接矩阵（或邻接表）存储图的结构。
3. 从sourcesourcesource出发进行BFS\texttt{BFS}BFS：
   • 初始化一个队列，将sourcesourcesource入队。
   • 维护一个全局权重计数器w=1w = 1w=1。
   • 当队列非空时，弹出队首节点uuu，遍历所有与uuu相邻的节点vvv，如果边(u,v)(u,v)(u,v)尚未被分配权重，则将其权重设为www，并将www加111，同时将vvv入队，并标记该边已分配。
4. BFS\texttt{BFS}BFS结束后，每条边都被赋予了一个唯一的权重（111到mmm）。
5. 按输入顺序输出每条边的端点及对应的新权重。

复杂度分析

• BFS\texttt{BFS}BFS遍历所有节点和边，时间复杂度为O(n+m)O(n + m)O(n+m)。
• 使用邻接矩阵（n≤2500n \le 2500n≤2500）时，每次检查所有邻居需要O(n2)O(n^2)O(n2)，但nnn较小，可以接受。也可以使用邻接表优化到O(n+m)O(n + m)O(n+m)。
• 空间复杂度O(n2)O(n^2)O(n2)（邻接矩阵）或O(n+m)O(n + m)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>usingnamespacestd;constintMAXN=2505;intn,m,source;intg[MAXN][MAXN];// 存储分配后的边权，-1 表示无边intorigU[25005],origV[25005];// 保存输入顺序的端点boolvisited[MAXN][MAXN];// 标记边是否已在 BFS 中被分配voidbfs(){queue<int>q;intweight=1;q.push(source);while(!q.empty()){intu=q.front();q.pop();for(intv=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);}}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;for(intcs=1;cs<=T;++cs){cin>>n>>m>>source;// 初始化邻接矩阵memset(g,-1,sizeof(g));memset(visited,false,sizeof(visited));for(inti=0;i<m;++i){intw;cin>>origU[i]>>origV[i]>>w;// 仅标记存在边，权重暂存为 0（后续被覆盖）g[origU[i]][origV[i]]=g[origV[i]][origU[i]]=0;}bfs();cout<<"Case "<<cs<<":\n";for(inti=0;i<m;++i)cout<<origU[i]<<' '<<origV[i]<<' '<<g[origU[i]][origV[i]]<<'\n';}return0;}

总结

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

核心要点：

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