刷题笔记合集🔗

5G网络建设

问题描述

某城市需要进行5G网络建设，已经选取 个地点设置5G基站，编号固定为 到 ，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间假设光纤的成本各不相同，且有些节点之间已经存在光纤相连。

请你设计算法，计算出能联通这些基站的最小成本是多少。

注意：基站的联通具有传递性，比如基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通。

输入格式

第一行输入表示基站的个数 ，其中：

第二行输入表示具备光纤直连条件的基站对的数目 ，其中：

从第三行开始连续输入 行数据，格式为:

其中： ， 表示基站的编号

表示在 、 之间架设光纤的成本

表示是否已存在光纤连接， 表示未连接， 表示已连接

输出格式

如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本。

如果给定条件，无法建设成功互联互通的5G网络，则输出 。

样例输入

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

3
1
1 2 5 0

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

样例输出

4

-1

1

数据范围

题解

这道题是经典的最小生成树问题。要理解这个问题，我们可以把基站看作图中的节点，而基站之间的光纤连接看作边。我们的目标是找到一种连接所有基站的方式，使得新建光纤的总成本最小。

最小生成树是一个包含图中所有顶点的无环连通子图，其权重（在本题中是光纤成本）之和最小。在这个问题中，我们需要注意一些基站之间已经有光纤连接（就像是免费的边），所以我们只需要计算新建光纤的成本。

对于这类问题，常用的算法有Kruskal和Prim算法。这里我采用Kruskal算法解决：

1. 首先将所有可能连接的基站对按成本从小到大排序
2. 然后逐一选择成本最小的连接，如果这个连接不会导致环路的产生，就将它加入到我们的网络中
3. 重复步骤2，直到所有基站都连通或者无法连通

具体实现中，我们需要使用并查集来检测是否形成环。并查集是一种树形的数据结构，用于处理不相交集合的合并及查询问题。

算法的时间复杂度主要来自于对边的排序，为 ，其中 是边的数量。而空间复杂度为 ，其中 是节点数。

这种解法对于题目给定的数据范围（，）来说是很高效的，可以轻松处理所有测试用例。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()

# 并查集实现
class UF:
    def __init__(self, n):
        # 初始化父节点数组
        self.p = list(range(n + 1))
        # 集合数量
        self.cnt = n
    
    def find(self, x):
        # 路径压缩
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    
    def union(self, x, y):
        # 合并两个集合
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[rx] = ry
            self.cnt -= 1
            return True
        return False

def solve():
    # 读取基站数量和可连接的基站对数量
    n = int(input())
    m = int(input())
    
    # 存储所有边信息
    edges = []
    # 已经存在的连接数量
    exist = 0
    
    # 读取所有边的信息
    for _ in range(m):
        x, y, z, p = map(int, input().split())
        if p == 1:
            # 已存在的连接
            edges.append((x, y, 0, 1))
            exist += 1
        else:
            # 未连接的边
            edges.append((x, y, z, 0))
    
    # 按成本排序
    edges.sort(key=lambda e: e[2])
    
    # 初始化并查集
    uf = UF(n)
    
    # 先合并已存在的连接
    for x, y, _, p in edges:
        if p == 1:
            uf.union(x, y)
    
    # 最小成本
    cost = 0
    
    # Kruskal算法
    for x, y, z, p in edges:
        if p == 0 and uf.union(x, y):
            cost += z
    
    # 检查是否所有节点都已连通
    return cost if uf.cnt == 1 else -1

print(solve())

• Cpp

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

// 边结构体
struct Edge {
    int from, to, cost, exist;