顶点加权图的k连通划分 python

以下是一个基于Python的顶点加权图的k连通划分算法的实现：

from typing import List
from queue import PriorityQueue

def k_conn_partition(n: int, edges: List[List[int]], k: int) -> List[List[int]]:
    # 构建邻接表和边权矩阵
    adj_list = [[] for _ in range(n)]
    adj_matrix = [[0] * n for _ in range(n)]
    for a, b, w in edges:
        adj_list[a].append(b)
        adj_list[b].append(a)
        adj_matrix[a][b] = adj_matrix[b][a] = w
    
    # 用Dijkstra算法求出每个点到其他点的最短路
    def dijkstra(s: int) -> List[int]:
        dist = [float('inf')] * n
        dist[s] = 0
        visited = [False] * n
        pq = PriorityQueue()
        pq.put((0, s))
        while not pq.empty():
            d, u = pq.get()
            if visited[u]:
                continue
            visited[u] = True
            for v in adj_list[u]:
                if not visited[v]:
                    new_d = d + adj_matrix[u][v]
                    if new_d < dist[v]:
                        dist[v] = new_d
                        pq.put((new_d, v))
        return dist
    
    # 计算任意两点之间的最短路
    shortest_paths = [[0] * n for _ in range(n)]
    for i in range(n):
        shortest_paths[i] = dijkstra(i)
    
    # 用DFS找出连通块并计算总权值
    def dfs(u: int, visited: List[bool], group: List[int], total_weight: int) -> None:
        visited[u] = True
        group.append(u)
        for v in adj_list[u]:
            if not visited[v]:
                dfs(v, visited, group, total_weight + adj_matrix[u][v])
        return total_weight
    
    # 对于每个连通块，找出其内部的所有点之间的最短路
    groups = []
    visited = [False] * n
    for i in range(n):
        if not visited[i]:
            group = []
            total_weight = dfs(i, visited, group, 0)
            group_shortest_paths = [[0] * len(group) for _ in range(len(group))]
            for j in range(len(group)):
                for k in range(j+1, len(group)):
                    group_shortest_paths[j][k] = group_shortest_paths[k][j] = shortest_paths[group[j]][group[k]]
            groups.append((total_weight, group, group_shortest_paths))
    
    # 将所有连通块按总权值从小到大排序
    groups.sort()
    
    # 用Kruskal算法将连通块合并
    parent = list(range(n))
    def find(x: int) -> int:
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    def union(x: int, y: int) -> None:
        px, py = find(x), find(y)
        if px != py:
            parent[px] = py
    result = []
    for i in range(len(groups)):
        total_weight, group, group_shortest_paths = groups[i]
        if i < k-1 or (i == k-1 and len(groups) == k):
            for j in range(len(group)):
                for k in range(j+1, len(group)):
                    if find(group[j]) != find(group[k]):
                        result.append([group[j], group[k]])
                        union(group[j], group[k])
        else:
            # 对于剩下的连通块，找到最短的跨越两个连通块的边
            bridge_weight = float('inf')
            u, v = -1, -1
            for j in range(i):
                for x in range(len(groups[j][1])):
                    for y in range(len(group)):
                        if groups[j][1][x] < group[y]:
                            w = groups[j][0] + total_weight - group_shortest_paths[x][y]
                            if w < bridge_weight:
                                bridge_weight = w
                                u, v = groups[j][1][x], group[y]
            result.append([u, v])
            for j in range(len(group)):
                for k in range(j+1, len(group)):
                    if find(group[j]) != find(group[k]):
                        union(group[j], group[k])
    return result

该算法的时间复杂度为$O(n^3\log n)$，其中$n$为顶点数。