E卷-刷题笔记合集🔗

问题描述

小兰负责一个城市的5G网络建设项目。现在需要在城市中选取 个地点建设5G基站，这些基站编号为 到 。为了确保基站之间能够互联互通，需要用光纤将基站连接起来。

不同基站之间铺设光纤的成本各不相同，有些基站之间已经存在光纤连接。请帮助小兰设计一个算法，计算能够让所有基站互联互通的最小成本。

注意：基站的连通具有传递性。如果基站 A 与基站 B 之间有光纤，基站 B 与基站 C 之间也有光纤，则基站 A 与基站 C 也可以互相通信。

输入格式

第一行输入一个正整数 ，表示基站的数量。

第二行输入一个正整数 ，表示可以直接连接的基站对数量。

接下来 行，每行包含四个整数 、、、：

• 和 表示两个基站的编号
• 表示在这两个基站之间铺设光纤的成本
• 表示这两个基站是否已经存在光纤连接， 表示未连接， 表示已连接

输出格式

输出一个整数，表示使所有基站互联互通的最小成本。

如果无法让所有基站互联互通，则输出 。

样例输入1

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

样例输出1

4

样例输入2

3
1
1 2 5 0

样例输出2

-1

样例输入3

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

样例输出3

1

样例解释

数据范围

• 
• 
• 且
• 
• 

题解

这是一个最小生成树问题的变种。与普通的最小生成树问题相比，本题的特殊之处在于有些边已经存在（即P=1的情况）。

解题思路:

1. 对于已经存在光纤连接的基站对(P=1)，可以将它们之间的边权重设为0，因为使用这些已有的连接不需要额外成本。

2. 对于未连接的基站对(P=0)，边权重就是铺设光纤的成本Z。

3. 然后就可以使用经典的最小生成树算法来求解:

   • 可以用Prim算法:从任意节点开始，每次选择与当前连通部分距离最近的点加入
   • 也可以用Kruskal算法:将所有边按权重排序，依次选择不会形成环的边

4. 如果最后能够将所有节点连通，则输出最小生成树的总权重（即最小成本） 如果无法将所有节点连通，则输出-1

时间复杂度:

• Prim算法:
• Kruskal算法:

对于本题的数据范围()，两种算法都可以通过。

参考代码

def find_set(x, p_arr):
    """查找并查集的根节点"""
    if p_arr[x] != x:
        p_arr[x] = find_set(p_arr[x], p_arr)
    return p_arr[x]

class UnionSet:
    def __init__(self, n):
        self.p_arr = [i for i in range(n)]
        self.size = n
        
    def find(self, x):
        if x != self.p_arr[x]:
            self.p_arr[x] = self.find(self.p_arr[x])
        return self.p_arr[x]
    
    def union(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            self.p_arr[py] = px
            self.size -= 1

def kruskal():
    # 读取输入
    n = int(input())
    m = int(input())
    
    # 存储边信息
    e_arr = []
    for _ in range(m):
        u, v, w, p = map(int, input().split())
        # 已连接边权为0
        c = 0 if p else w
        e_arr.append([u, v, c])
    
    # 按边权排序    
    e_arr.sort(key=lambda x: x[2])
    
    # 初始化并查集
    us = UnionSet(n + 1)
    
    # 最小生成树
    cost = 0
    for u, v, w in e_arr:
        if us.find(u) != us.find(v):
            cost += w
            us.union(u, v)
            if us.size == 2:
                return cost
                
    return -1

if __name__ == "__main__":
    print(kruskal())

#include <bits/stdc++.h>
using namespace std;

// 边结构
struct Edge {
    int u, v, w;
    Edge(int src, int dst, in