#4023
1348. 【例4-9】城市公交网建设问题
1348. 【例4-9】城市公交网建设问题
题目描述
有一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权为在这两个城市之间修建高速公路的造价,研究后发现,这个地图有一个特点,即任一对城市都是连通的。现在的问题是,要修建若干高速公路把所有城市联系起来,问如何设计可使得工程的总造价最少?
输入格式
第一行两个整数 n、e(2≤n≤100,e≥n−1),表示城市数和边数。接下来 e 行,每行 i、j、w,表示城市 i、j 间一条无向道路的造价;1≤i,j≤n,1≤w≤2147483647。输入图连通,允许重边和自环;自环不能用于连接不同城市,同一对城市间可以选造价最低的道路。输出格式
输出 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 81 2
2 3
3 4
3 5
来源
一本通在线评测 ybtbas-1348