#zDLlydlt60x6105. 观光之旅 Sightseeing Trip
观光之旅 Sightseeing Trip
好的,这是整理好的完整题目描述,包含样例解释,格式清晰,适合上传平台。
题目描述
给定一张无向图,求图中一个至少包含 个点的环,要求:
- 环上节点不重复。
- 环上边的长度之和最小。
这个问题称为无向图的最小环问题。
你需要输出最小环的节点顺序(按环的顺序),如果最小环不唯一,输出任意一个均可。
如果图中不存在至少 个点的环,则输出 No solution.。
输入格式
第一行两个整数 和 ,表示图的点数和边数。
接下来 行,每行三个整数 ,表示点 和点 之间有一条无向边,长度为 。
输出格式
输出一行,包含最小环的所有节点(按环顺序输出),用空格分隔。
如果不存在这样的环,输出 No solution.。
数据范围
输入样例
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
输出样例
1 3 5 2
样例解释
图的构造
点数 ,边数 ,边如下(为了方便,重复边取最小长度,因为是无向图):
- 1-4: 1
- 1-3: 300(但下面有一条更小的 1-3 边,见第 3 条)
- 1-3: 10(长度 10 替换上面的 300)
- 1-2: 16
- 2-3: 100
- 2-5: 15
- 5-3: 20
注意:输入中 1-3 有两条不同长度边(300 和 10),应取较短的那条(10)作为实际距离,因为这是无向图的最小环问题,边权取实际最小权。
寻找最小环
环至少 3 个点。
考虑几个候选环:
- 环 1-2-3:边长 16 + 100 + 10 = 126
- 环 1-3-5-2:边长 10 + 20 + 15 + 16 = 61
- 1→3: 10
- 3→5: 20
- 5→2: 15
- 2→1: 16
- 环 2-3-5:边长 100 + 20 + 15 = 135
- 环 1-4-?:1-4 只有一条边 1,4 只连 1,无法构成环(至少 3 个点)。
显然 环 1-3-5-2 长度 61 是当前最小的。
是否有更小的?
检查环 1-2-5-3:
1→2: 16
2→5: 15
5→3: 20
3→1: 10
总和 16+15+20+10 = 61,与上面相同(只是顺序不同)。
所以 61 是最小值。
输出方案
输出可以是 1 3 5 2(按环顺序)。
也接受 1 2 5 3 等,只要是一个长度为 61 的环即可。
最终输出:1 3 5 2