🛣️🐾《兔猫信奥学院·最省钱的高速公路》🧩

🏫 题目背景

在 兔猫信奥学院 的“城市规划实验室”里，加菲老师摊开了一张城市地图。 小兔负责算预算，小猫负责画路线。老师说：

“我们要修高速公路把所有城市都连起来，但学院经费有限，总造价必须尽可能小。 你们不仅要算出最小造价，还要给出具体修哪几条路。”

地图上每条潜在高速公路都有一个造价（权值）。研究后发现：任意两座城市之间都有路径可达（也就是整张图是连通的）。

📌 任务描述

给定一个包含 (n) 个城市、(e) 条候选道路的连通无向图：

• 顶点：城市 (1..n)
• 边：$(i,j)$ 表示城市 $(i)$ 与城市$(j)$之间可修高速
• 权值：$(w_{ij})$为修建该高速的造价

你需要选择 恰好 (n-1) 条道路，使得：

1. 所有城市都被连通（任意两城可互相到达）
2. 总造价最小
3. 输出你选择的这 (n-1) 条道路（每行两个城市编号）

这就是经典的 最小生成树（MST） 问题。

✅ 输入格式

第一行两个整数：

• (n)：城市数 $(1 \le n \le 100)$
• (e)：候选道路数

接下来 (e) 行，每行三个整数$(i, j, w_{ij})$表示： 在城市 (i) 和城市 (j) 之间修建高速公路的造价为 $(w_{ij})$。 （无向边，造价为正整数）

✅ 输出格式

输出$(n-1)$ 行，每行两个整数 $(u\ v)$，表示在城市 (u) 与城市 $(v)$之间修建一条高速公路。

• 只要输出的 (n-1) 条边能构成一棵 最小生成树，就视为正确。
• 若存在多种最小生成树，输出任意一种即可。

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

一种可能的输出：

1 2
2 3
3 4
3 5

🧠 样例解释（加菲老师的讲评）

我们有 5 个城市，因此最终必须选 (n-1=4) 条路。

把候选道路按造价从小到大看（只为解释，不要求你这么输出）：

• (1-2) 造价 2 ✅
• (3-5) 造价 3 ✅
• (3-4) 造价 6 ✅
• (2-3) 造价 8 ✅ （此时 1,2,3,4,5 全部连通）

总造价：(2 + 3 + 6 + 8 = 19)，并且所有城市连通，且没有浪费的环路，因此是一棵最小生成树。

注意：样例输出给的是另一棵同样最优的生成树（也可能造价一样），题目允许输出任意一种最优方案。

1 0

🧠 样例解释

只有 1 个城市，本来就“全部连通”，不需要修路，所以输出为空（0 行）。

📏 数据范围与提示

• $(1 \le n \le 100)$
• 图保证连通
• 典型做法：Kruskal（并查集） 或 Prim
• 输出只要是一棵 最小生成树 即可