解题思路：最小生成树中的最长边问题

1. 问题理解

我们需要在给定的城镇网络中找到一种高速公路修建方案，使得：

• 所有城镇都能互相连通（形成连通图）
• 所有修建的高速公路中最长的那条要尽可能短

这实际上是要找到图的最小生成树（Minimum Spanning Tree, MST），然后找出这个生成树中最长的边。

2. 算法选择

使用Prim算法来求解最小生成树，因为：

• 适合稠密图（城镇数量N≤500，是完全图）
• 时间复杂度O(N²)在本题数据范围内可行
• 可以方便地记录生成树中的所有边权

3. 具体实现步骤

1. 输入处理

   • 读取测试用例数量T
   • 对每个测试用例：
     • 读取城镇数量N
     • 读取N×N的距离矩阵

2. Prim算法初始化

   • 将每个城镇到自己的距离设为INF（不可达）
   • 初始化lowcost数组，记录从已选城镇到未选城镇的最小距离
   • 初始化vis数组标记城镇是否已加入生成树
   • 从第一个城镇开始构建生成树

3. 构建最小生成树

   • 每次循环： a. 在未选择的城镇中，找到距离当前生成树最近的城镇 b. 将该城镇加入生成树 c. 记录这条边的权值 d. 更新其他未选城镇到生成树的最小距离

4. 寻找最长边

   • 在生成树的所有边中，找出权值最大的那条

5. 输出结果

   • 对每个测试用例，输出生成树中最长边的长度

4. 关键点说明

• 距离矩阵处理：对角线元素设为INF，避免自环
• 贪心策略：Prim算法每次选择最短的边加入生成树
• 最长边记录：在构建生成树时保存所有边的权值，最后找出最大值
• 输入优化：使用scanf提高读取速度（题目提示输入量较大）

5. 复杂度分析

• 时间复杂度：O(T×N²)，其中T是测试用例数，N是城镇数
• 空间复杂度：O(N²)存储距离矩阵

6. 示例解析

以题目中的样例输入为例：

3
0 990 692
990 0 179
692 179 0

算法执行过程：

1. 从城镇1开始
2. 选择最短边1-3（692）
3. 然后选择3-2（179）
4. 生成树包含两条边692和179
5. 最长边是692

7. 为什么这样做是正确的？

根据最小生成树的性质：

• 所有生成树中，Prim算法得到的生成树总权值最小
• 在这个最小的总权值生成树中，最长边也是所有可能生成树中最长边里最小的
• 这正好符合题目"最小化最长公路"的要求

标程

#include <cstdio>  // 使用C++标准库的stdio
#include<iostream>
#define MAX 500     // 最大城市数量
#define INF 0x3f3f3f3f  // 定义一个很大的数表示无穷大

int a[MAX][MAX];    // 城市间的距离矩阵
int lowcost[MAX];   // 记录最小生成树的最小边权
int vis[MAX];       // 记录城市是否被访问过
int b[MAX];         // 存储最小生成树的边权

int main() {
	int ExampleNumber; // 测试用例数量
	int N;          // 城市数量
	int i, j, k;    // 循环变量
	int maxx;       // 最长公路长度
	int minn;       // 临时最小值
	
	// 读取测试用例数量
	scanf("%d", &ExampleNumber);
	
	// 处理每个测试用例
	while (ExampleNumber--) {
		// 读取城市数量
		scanf("%d", &N);
		
		// 读取城市间距离矩阵
		for (i = 1; i <= N; i++) {
			for (j = 1; j <= N; j++) {
				scanf("%d", &a[i][j]);
			}
		}
		
		// 初始化
		for (i = 1; i <= N; i++) {
			a[i][i] = INF;      // 城市自己到自己的距离设为无穷大
			lowcost[i] = a[1][i]; // 初始化从城市1到其他城市的距离
			vis[i] = 0;         // 所有城市初始未访问
		}
		
		vis[1] = 1;  // 从城市1开始
		
		// Prim算法求最小生成树
		for (i = 1; i < N; i++) {
			minn = INF;
			// 找出当前未访问城市中距离最小的
			for (j = 1; j <= N; j++) {
				if (minn > lowcost[j] && vis[j] == 0) {
					minn = lowcost[j];
					k = j;  // 记录最小距离的城市
				}
			}
			
			vis[k] = 1;  // 标记为已访问
			b[i] = minn; // 存储这条边的权值
			
			// 更新lowcost数组
			for (j = 1; j <= N; j++) {
				if (vis[j] == 1) {
					lowcost[j] = INF;  // 已访问的城市设为无穷大
				}
				if (vis[j] == 0 && a[k][j] < lowcost[j]) {
					lowcost[j] = a[k][j];  // 更新到未访问城市的最小距离
				}
			}
		}
		
		// 找出最小生成树中最长的边
		maxx = 0;
		for (i = 1; i < N; i++) {
			if (maxx < b[i]) {
				maxx = b[i];
			}
		}
		
		// 输出结果
		printf("%d\n", maxx);
	}
	
	return 0;
}