#P3219. 5G网络建设(200分)
-
1000ms
Tried: 91
Accepted: 34
Difficulty: 4
所属公司 :
华为od
5G网络建设(200分)
题目思路
题目意思就是给你一张图,有一些边已经连接上。问你联通整张图的最小花费。(这个最小花费就是你选择的边的权值的和)
如果大家对算法设计/数据结构这门课还有印象,应该能够反应出来,这就是最小生成树问题,我这里使用的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