题目描述

现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间架设光纤的成本各不相同，且有些节点之间已经存在光纤相连，请你设计算法，计算出能联通这些基站的最小成本是多少。注意，基站的联通具有传递性，入基站A与基站B架设了光纤基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通

输入描述

第一行输入表示基站的个数N，其中0<N<=20

题目思路

题目意思就是给你一张图，有一些边已经连接上。问你联通整张图的最小花费。（这个最小花费就是你选择的边的权值的和）

如果大家对算法设计/数据结构这门课还有印象，应该能够反应出来，这就是最小生成树问题，我这里使用的KRUSKAL算法。不会的同学可以看百度自学KRUSKAL算法。

需要注意的是，题目里说的那些已经连上的边(P = 1)，我们可以直接看作是花费为0的边，我们直接放入。然后对于剩下的边，我们照常使用KRUSKAL即可。

Java代码