5G网络建设 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

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

题解

最小生成树的问题，可以使用 Kruskal 算法进行求解。

初始化并查集，每个基站初始时属于一个独立的集合。
将已经存在光纤连接的基站合并到同一个集合中。
将未连接的光纤按照成本从小到大排序。
遍历排序后的光纤，将两个基站连接，如果两个基站已经属于同一个集合，则不连接。
判断所有基站是否属于同一个集合，如果是，则输出总成本，否则输出-1。

Kruskal 算法的步骤：

初始化： 将每个顶点视为一个独立的集合，每个集合中只包含一个顶点。将图中的所有边按照权值从小到大排序。
遍历边： 从权值最小的边开始遍历，如果该边连接的两个顶点不在同一个集合中，则选择这条边，并将这两个顶点所在的集合合并为一个集合。重复此步骤直到所有顶点都在同一个集合中。
输出结果： 最终得到的就是最小生成树。

Java

import java.util.Comparator;
import java.util.Scanner;
import java.util.Vector;
/*** @author code5bug*/
class Main {static int[] fa;static int find(int x) {if (fa[x] == x) return x;return fa[x] = find(fa[x]);}static void merge(int x, int y) {int fx = find(x), fy = find(y);fa[fx] = fy;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 基站个数, 具备光纤直连条件的基站对的数目int N = scanner.nextInt(), M = scanner.nextInt();fa = new int[N + 1];for (int i = 1; i <= N; i++) {fa[i] = i;}Vector<Plan> plans = new Vector<>();for (int i = 0; i < M; i++) {Plan p = new Plan();p.x = scanner.nextInt();  p.y = scanner.nextInt();p.z = scanner.nextInt();  p.p = scanner.nextInt();// 已经存在光纤if (p.p == 1) {merge(p.x, p.y);} else {plans.add(p);}}plans.sort(Comparator.comparingInt(a -> a.z));int cost = 0;for (Plan p : plans) {// 没有连接则连接上if (find(p.x) != find(p.y)) {cost += p.z;merge(p.x, p.y);}}// 所有基站是否连接boolean allConnected = true;for (int i = 1; i <= N; i++) {if (find(i) != find(1)) {allConnected = false;break;}}System.out.println(allConnected ? cost : -1);}
}class Plan {int x, y; // 基站的编号int z, p; // 架设光纤的成本, 是否已存在光纤连接，0表示未连接1表示已连接
}

Python

class Plan:def __init__(self, x, y, z, p):self.x = x  # 基站的编号self.y = y  # 基站的编号self.z = z  # 架设光纤的成本self.p = p  # 是否已存在光纤连接，0表示未连接，1表示已连接def find(x, fa):if fa[x] == x:return xfa[x] = find(fa[x], fa)return fa[x]def merge(x, y, fa):fx, fy = find(x, fa), find(y, fa)fa[fx] = fydef main():N, M = int(input()), int(input())fa = [i for i in range(N+1)]plans = []for _ in range(M):x, y, z, p = map(int, input().split())if p == 1:merge(x, y, fa)else:plans.append(Plan(x, y, z, p))plans.sort(key=lambda p: p.z)cost = 0for p in plans:if find(p.x, fa) != find(p.y, fa):cost += p.zmerge(p.x, p.y, fa)all_connected = all(find(i, fa) == find(1, fa) for i in range(1, N+1))print(cost if all_connected else -1)if __name__ == "__main__":main()

C++

#include <bits/stdc++.h>
using namespace std;struct plan{int x, y; // 基能的编号int z, p; // 架设光纤的成本, 是否已存在光纤连接，0表示未连接1表示已连接
};int fa[30];int find(int x){if(fa[x] == x) return x;return fa[x] = find(fa[x]);
}void merge(int x, int y){int fx = find(x), fy = find(y);fa[fx] = fy;
}int main(){int N, M;// 基站个数, 具备光纤直连条件的基站对的数目cin >> N >> M;for(int i=1;i<=N;i++) fa[i] = i;vector<plan> plans;for(int i=0;i<M;i++){plan p;cin >> p.x >> p.y >> p.z >> p.p;// 已经存在光纤if(p.p == 1) merge(p.x, p.y);else plans.push_back(p);}sort(plans.begin(), plans.end(), [](plan a, plan b){return a.z < b.z;});int cost = 0;for(auto& p : plans){// 没有连接则连接上if(find(p.x) != find(p.y)){cost += p.z;merge(p.x, p.y);}}// 所有基站是否连接bool all_connected = true;for(int i=1;i<=N;i++){if(find(i) != find(1)){all_connected = false;break;}}cout << (all_connected ? cost : -1) << endl;return 0;
}