题目思路

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

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

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

Java代码

题目内容

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

输入描述

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

第二行输入表示具备光纤直连条件的基站对的数目$M$,其中$0 < M < N * (N - 1) / 2$

从第三行开始连域输入$M$行数据，将式为$X\ Y\ Z\ P$，其中$X \ Y$表示基能的编号，$0<X<=N$， $0 < Y<=N$ 且$x$不等于$y$， $z$表示在$X\ Y$之间架设光纤的成本，其中$0 < Z < 100$，$P$表示是否已存在光纤连接，$0$表示未连接$1$表示已连接.

输出描述

如果给定条件，可以建设成功互联与通的$5G$网络，则输出最小的建设成本， 如果给定条件，无法建设成功互联与通的$5G$网络，则输出$-1$

样例1

输入

3
3
1 2 3 0
1 3 1 0
2 3 5 0

输出

4

说明

只需要在$1.2$以及$2,3$基站之间铺设光纤，其成本为$3+1=4$

样例2

输入

3
1
1 2 5 0

输出

-1

说明

$3$基站无法与其他基站连接，输出$-1$

样例3

输入

3
3
1 2 3 0
1 3 1 0
2 3 5 1

输出

1

说明

$2.3$基站已有光纤相连，只有要再$1.3$站点$2$向铺设,其成本为$1$