题目思路

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

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

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

Java代码

import java.util.*;

class Main {
    static int[] fa = new int[200];
    static List<Integer[]> a = new ArrayList<>();
    
    // 合并两个集合，返回是否成功合并
    public static int merge(int x , int y){
        int fx = getfa(x);
        int fy = getfa(y);
        if (fx == fy) return 0;
        fa[fx] = fy;
        return 1;
    }
    
    // 使用路径压缩找到节点x的根节点
    public static int getfa(int x){
        if (fa[x] == x) return x;
        return fa[x] = getfa(fa[x]);
    }
    
    public static void init (){
        // 初始化并查集
        for (int i = 1 ; i < fa.length ; i++){
            fa[i] = i;
        }
    }
    public static void main (String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 读取节点数
        int m = sc.nextInt(); // 读取边数
        
        init();
        
        for (int i = 1 ; i <= m ; i++){
            int x = sc.nextInt(); // 边的起始节点
            int y = sc.nextInt(); // 边的结束节点
            int z = sc.nextInt(); // 边的权重
            int p = sc.nextInt(); // 是否预先连接的标志
            
            if (p == 1) merge(x , y); // 如果标志为1，直接合并两个节点
            else {
                a.add(new Integer[]{x , y , z}); // 否则将边加入到边列表中
            }
        }
        
        // 按照边的权重进行排序
        a.sort((a , b) -> {
            return a[2].compareTo(b[2]);
        });
        
        int ans = 0;
        for (Integer[] x : a){
            if (merge(x[0] , x[1]) == 1) ans += x[2]; // 如果成功合并两个节点，累加权重
        }
        
        // 判断所有节点是否联通
        boolean ok = true;
        for(int i = 1 ; i <= n ; i++) {
        	if(getfa(i) != getfa(1)) ok = false;
        }
        
        if (ok) {
        	System.out.println(ans); // 如果所有节点联通，输出最小花费
        }
        else {
        	System.out.println(-1); // 否则输出-1
        }
        
        return ;
    }
}

C++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int fa[200];
vector<vector<int>> a;


// 使用路径压缩找到节点x的根节点
int getfa(int x) {
    if (fa[x] == x) return x;
    return fa[x] = getfa(fa[x]);
}

// 合并两个集合，返回是否成功合并
int merge(int x, int y) {
    int fx = getfa(x);
    int fy = getfa(y);
    if (fx == fy) return 0;
    fa[fx] = fy;
    return 1;
}

void init() {
    // 初始化并查集
    for (int i = 1; i < 200; i++) {
        fa[i] = i;
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 读取节点数和边数

    init();

    for (int i = 1; i <= m; i++) {
        int x, y, z, p;
        cin >> x >> y >> z >> p; // 读取边的起始节点、结束节点、权重和标志

        if (p == 1) merge(x, y); // 如果标志为1，直接合并两个节点
        else {
            a.push_back({x, y, z}); // 否则将边加入边列表
        }
    }

    // 按边的权重排序
    sort(a.begin(), a.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
    });

    int ans = 0;
    for (const auto& x : a) {
        if (merge(x[0], x[1]) == 1) ans += x[2]; // 如果成功合并两个节点，累加权重
    }

    // 判断所有节点是否联通
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        if (getfa(i) != getfa(1)) ok = false;
    }

    if (ok) {
        cout << ans << endl; // 如果所有节点联通，输出最小花费
    }
    else {
        cout << -1 << endl; // 否则输出-1
    }

    return 0;
}

Python代码

fa = [i for i in range(200)]
a = []

def getfa(x):
    if fa[x] == x:
        return x
    fa[x] = getfa(fa[x])
    return fa[x]
# 合并两个集合，返回是否成功合并
def merge(x, y):

    fx = getfa(x)
    fy = getfa(y)
    if fx == fy:
        return 0
    fa[fx] = fy
    return 1

def init():
    # 初始化并查集
    for i in range(1, 200):
        fa[i] = i

n = int(input())
m = int(input())

init()

for i in range(1, m + 1):
    x, y, z, p = map(int, input().split())  # 读取边的起始节点、结束节点、权重和标志

    if p == 1:
        merge(x, y)  # 如果标志为1，直接合并两个节点
    else:
        a.append([x, y, z])  # 否则将边加入边列表

# 按边的权重排序
a.sort(key=lambda x: x[2])

ans = 0
for x in a:
    if merge(x[0], x[1]) == 1:
        ans += x[2]  # 如果成功合并两个节点，累加权重

# 判断所有节点是否联通
ok = True
for i in range(1, n + 1):
    if getfa(i) != getfa(1):
        ok = False

if ok:
    print(ans)  # 如果所有节点联通，输出最小花费
else:
    print(-1)  # 否则输出-1

Js代码

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    // write your code here!

    const fa = Array.from({ length: 200 }, (_, i) => i);
    const a = [];
    function getfa(x) {
        if (fa[x] == x) {
            return x;
        }
        fa[x] = getfa(fa[x]);
        return fa[x];
    }
    // 合并两个集合，返回是否成功合并
    function merge(x, y) {

        const fx = getfa(x);
        const fy = getfa(y);
        if (fx == fy) {
            return 0;
        }
        fa[fx] = fy;
        return 1;
    }

    function init() {
        // 初始化并查集
        for (let i = 1; i < 200; i++) {
            fa[i] = i;
        }
    }

    const n = Number(lines[0]);
    const m = Number(lines[1]);

    init();

    for (let i = 1; i <= m; i++) {
        const [x, y, z, p] = lines[i + 1].trim().split(' ').map(Number); // 读取边的起始节点、结束节点、权重和标志

        if (p === 1) {
            merge(x, y); // 如果标志为1，直接合并两个节点
        } else {
            a.push([x, y, z]); // 否则将边加入边列表
        }
    }

    // 按边的权重排序
    a.sort((a, b) => a[2] - b[2]);

    let ans = 0;
    for (const x of a) {
        if (merge(x[0], x[1]) == 1) {
            ans += x[2]; // 如果成功合并两个节点，累加权重
        }
    }

    // 判断所有节点是否联通
    let ok = true;
    for (let i = 1; i <= n; i++) {
        if (getfa(i) !== getfa(1)) {
            ok = false;
            break;
        }
    }

    if (ok) {
        console.log(ans); // 如果所有节点联通，输出最小花费
    } else {
        console.log(-1); // 否则输出-1
    }
});

题目内容

现需要在某城市进行$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$