5G网络建设 - 华为OD统一考试(C卷)
OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
现需要在某城市进行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 x
fa[x] = find(fa[x], fa)
return fa[x]
def merge(x, y, fa):
fx, fy = find(x, fa), find(y, fa)
fa[fx] = fy
def 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 = 0
for p in plans:
if find(p.x, fa) != find(p.y, fa):
cost += p.z
merge(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;
}
相关练习题
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#面经##春招##校招##秋招##华为#
海信集团二面8人在聊