5 最小生成树 5题

sy396: 最小生成树-Prim算法 简单

https://sunnywhy.com/sfbj/10/5/396

现有一个共个顶点、条边的无向图（假设顶点编号为从0到n-1），每条边有各自的边权。在图中寻找一棵树，使得这棵树包含图上所有顶点、所有边都是图上的边，且树上所有边的边权之和最小。使用Prim算法求出这个边权之和的最小值。

输入

第一行两个整数n、m（$1\le n\le 100,0\le m\le \frac{n(n-1)}{2}$），分别表示顶点数、边数；

接下来m行，每行三个整数u、v、w（$0\le u\le n-1,0\le v\le n-1,u\ne v,1\le w\le 100$），表示一条边的两个端点的编号及边权距离。数据保证不会有重边。

输出

输出一个整数，表示最小的边权之和。如果不存在这样的树，那么输出-1。

样例1

输入

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

输出

4

解释

对应的无向图如下图所示。加粗的部分即为最小生成树，其边权之和为1+1+2=4。

样例2

输入

3 1
0 1 1

输出

-1

解释

由于此图不连通，因此不存在最小生成树。

以下是使用 Prim 算法求解的 Python 代码：

import heapq

def prim(graph, n):
    visited = [False] * n
    min_heap = [(0, 0)]  # (weight, vertex)
    min_spanning_tree_cost = 0

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)

        if visited[vertex]:
            continue

        visited[vertex] = True
        min_spanning_tree_cost += weight

        for neighbor, neighbor_weight in graph[vertex]:
            if not visited[neighbor]:
                heapq.heappush(min_heap, (neighbor_weight, neighbor))

    return min_spanning_tree_cost if all(visited) else -1

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        u, v, w = map(int, input().split())
        graph[u].append((v, w))
        graph[v].append((u, w))

    min_spanning_tree_cost = prim(graph, n)
    print(min_spanning_tree_cost)

if __name__ == "__main__":
    main()

sy397: 最小生成树-Kruskal算法 简单

https://sunnywhy.com/sfbj/10/5/397

现有一个共n个顶点、m条边的无向图（假设顶点编号为从0到n-1），每条边有各自的边权。在图中寻找一棵树，使得这棵树包含图上所有顶点、所有边都是图上的边，且树上所有边的边权之和最小。使用Kruskal算法求出这个边权之和的最小值。

输入

第一行两个整数n、m（$1\le n\le {10}^4,0\le m\le {10}^5$），分别表示顶点数、边数；

接下来m行，每行三个整数u、v、w（$0\le u\le n-1,0\le v\le n-1,u\ne v,1\le w\le 100$），表示一条边的两个端点的编号及边权。数据保证不会有重边。

输出

输出一个整数，表示最小的边权之和。如果不存在这样的树，那么输出-1。

样例1

输入

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

输出

4

解释

对应的无向图如下图所示。加粗的部分即为最小生成树，其边权之和为1+1+2=4。

Kruskal算法是一种用于寻找最小生成树的算法。它的基本思想是按照边的权值从小到大的顺序选择边，如果这条边连接的两个顶点不在同一连通分量中，则选择这条边，否则放弃这条边。重复这个过程，直到图中所有的顶点都在同一连通分量中。

在实现Kruskal算法时，我们需要使用并查集来维护图中的连通分量，以便于快速判断两个顶点是否在同一连通分量中。

以下是Kruskal算法的Python实现：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[px] = py
            if self.rank[px] == self.rank[py]:
                self.rank[py] += 1

def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    res = 0
    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            res += w
    if len(set(uf.find(i) for i in range(n))) > 1:
        return -1
    return res

n, m = map(int, input().split())
edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))
print(kruskal(n, edges))

这段代码首先定义了一个并查集类UnionFind，然后定义了kruskal函数来实现Kruskal算法。在kruskal函数中，我们首先创建一个并查集实例，然后按照边的权值对边进行排序。然后遍历每一条边，如果这条边连接的两个顶点不在同一连通分量中，就将这两个顶点合并到同一连通分量中，并将这条边的权值加到结果中。最后，如果图中的所有顶点都在同一连通分量中，就返回结果，否则返回-1。

可以看到，kruskal 算法的时间复杂度主要来源于对边进行排序，因此其时间复杂度是O(ElogE)，其中E为图的边数。显然 kruskal 适合顶点数较多、边数较少的情况，这和 prim算法恰好相反。于是可以根据题目所给的数据范围来选择合适的算法，即如果是稠密图(边多)，则用 prim 算法;如果是稀疏图(边少)，则用 kruskal 算法。

Sy398: 最小造路成本 中等

https://sunnywhy.com/sfbj/10/5/398

现有个城市（假设城市编号为从0到n-1），需要在城市之间建造道路（道路造好后视为双向连通）。已知不同城市间造路的成本，问至少需要多少成本可以让这个城市连通（不需要直接连通，能够间接连通即可）。

输入

第一行一个整数 n（$1\le n\le 100$），表示城市数；

接下来给出 n 行 n 列的整数矩阵，其中i号行j号列表示 i 号城市和 j 号城市之间的造路成本w（当 $i=j$ 时 $w=0$，当$i\ne j$时 $1\le w\le 100$，且 $w[i][j]==[wj][i]$）。

输出

输出一个整数，表示最小的造路成本。

样例1

输入

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

输出

4

解释

对应的无向图如下图所示。加粗的部分即为最小成本时所建造的道路，其成本之和为。

这是一个经典的最小生成树问题，可以使用Prim算法或者Kruskal算法来解决。这里我们使用Prim算法来解决这个问题。

Prim算法的基本思想是从一个顶点开始，每次选择一条连接已选顶点和未选顶点的最小边，直到所有的顶点都被选中。

以下是使用Prim算法解决这个问题的Python代码：

def minCost(n, cost):
    visited = [False] * n
    minCost = [float('inf')] * n
    minCost[0] = 0
    res = 0

    while True:
        v = -1
        for u in range(n):
            if not visited[u] and (v == -1 or minCost[u] < minCost[v]):
                v = u
        if v == -1:
            break
        visited[v] = True
        res += minCost[v]
        for u in range(n):
            minCost[u] = min(minCost[u], cost[v][u])

    return res

n = int(input())
cost = [list(map(int, input().split())) for _ in range(n)]
print(minCost(n, cost))

在这段代码中，我们首先初始化所有的顶点为未访问状态，然后设置每个顶点的最小造路成本为无穷大，然后将第一个顶点的最小造路成本设置为0。然后在循环中，我们每次选择一个未访问的顶点，其造路成本最小，然后将其标记为已访问，并将其造路成本加入到总成本中，然后更新所有与该顶点相连的顶点的最小造路成本。最后，当所有的顶点都被访问后，返回总成本。

sy399: 最大删除边权值 中等

https://sunnywhy.com/sfbj/10/5/399

现有一个共n个顶点、m条边的无向图（假设顶点编号为从0到n-1），每条边有各自的边权。从图中删掉一些边，但保持这个图依然连通。问能删掉的边的权值之和的最大值。

输入

第一行两个整数n、m（$1\le n\le 100,0\le m\le \frac{n(n-1)}{2}$），分别表示顶点数、边数；

接下来m行，每行三个整数u、v、w（$0\le u\le n-1,0\le v\le n-1,u\ne v,1\le w\le 100$），表示一条边的两个端点的编号及边权。数据保证不会有重边。

输出

输出一个整数，表示能删掉的边的权值之和的最大值。如果图不连通，那么输出-1。

样例1

输入

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

输出

6

解释

对应的无向图如下图所示。加粗的边是允许删去的最大边权之和的边，其边权之和为。

样例2

输入

3 1
0 1 1

输出

-1

解释

由于此图不连通，因此输出-1。

这是一个最小生成树问题的变种。我们可以先使用Kruskal算法找出最小生成树，然后将所有边的权值之和减去最小生成树的权值之和，就得到了能删掉的边的权值之和的最大值。

以下是使用Kruskal算法解决这个问题的Python代码：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            if self.rank[px] > self.rank[py]:
                self.parent[py] = px
            else:
                self.parent[px] = py
                if self.rank[px] == self.rank[py]:
                    self.rank[py] += 1

def maxEdgeRemoval(n, m, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x[2])
    total_weight = sum(edge[2] for edge in edges)
    mst_weight = 0
    for u, v, w in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst_weight += w
    if len(set(uf.find(i) for i in range(n))) > 1:
        return -1
    return total_weight - mst_weight

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]
print(maxEdgeRemoval(n, m, edges))

在这段代码中，我们首先定义了一个并查集类，用于处理图中的连通性问题。然后我们将所有的边按照权值排序，然后依次添加到最小生成树中，如果添加的边不会形成环，那么就将其添加到最小生成树中。最后，我们检查最小生成树是否包含了所有的顶点，如果没有，那么返回-1，否则返回所有边的权值之和减去最小生成树的权值之和。

sy400: 最小连通成本 中等

https://sunnywhy.com/sfbj/10/5/400

现有个城市（假设城市编号为从0到n-1），需要在城市之间建造道路（道路造好后视为双向连通）。已知不同城市间造路的成本，并给定若干城市编号，这些城市之间互相不需要建造新的道路就已经连通，问至少需要多少成本来建造新的道路，可以让这个城市连通（不需要直接连通，能够间接连通即可）。

输入

第一行两个整数n、k（$1\le n\le 100,0\le k\le n$），分别表示总城市数、已经连通的城市数；

接下来给出 n 行 n 列的整数矩阵，其中i号行j号列表示 i 号城市和 j 号城市之间的造路成本w（当 $i=j$ 时 $w=0$，当$i\ne j$时 $1\le w\le 100$，且 $w[i][j]==[wj][i]$）。

最后一行共k 个整数，表示已经连通的城市编号。

输出

输出一个整数，表示最小的连通成本。

样例1

输入

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

输出

2

解释

对应的无向图如下图所示。由于0号和1号顶点已经连通，因此只需要把加粗的边建造好，即可使四个顶点连通，且成本是最小的，其成本为。

这个问题可以通过修改Prim算法来解决。我们首先将已经连通的城市标记为已访问，然后在Prim算法的循环中，我们只选择未访问的城市。这样，我们就可以找到连接所有城市的最小成本。

以下是修改后的Prim算法的Python代码：

def minCost(n, k, cost, connected):
    visited = [False] * n
    minCost = [float('inf')] * n
    for city in connected:
        minCost[city] = 0
    res = 0

    while True:
        v = -1
        for u in range(n):
            if not visited[u] and (v == -1 or minCost[u] < minCost[v]):
                v = u
        if v == -1:
            break
        visited[v] = True
        res += minCost[v]
        for u in range(n):
            minCost[u] = min(minCost[u], cost[v][u])

    return res

n, k = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(n)]
connected = list(map(int, input().split()))
print(minCost(n, k, cost, connected))

在这段代码中，我们首先初始化所有的城市为未访问状态，然后设置每个城市的最小造路成本为无穷大，然后将已经连通的城市的最小造路成本设置为0。然后在循环中，我们每次选择一个未访问的城市，其造路成本最小，然后将其标记为已访问，并将其造路成本加入到总成本中，然后更新所有与该城市相连的城市的最小造路成本。最后，当所有的城市都被访问后，返回总成本。