将图的加权顶点分成q个不相交的连通分支 python

可以使用深度优先搜索（DFS）和贪心算法来解决这个问题。具体步骤如下：

1. 首先对图进行深度优先搜索，得到每个顶点的子树大小（即该顶点及其所有子节点的总数）和该子树内边权重的总和。

2. 对每个顶点按照子树大小进行排序，得到一个顺序列表。

3. 从列表中按顺序选取前q-1个顶点作为分割点，将整个图分成q个连通分支。

具体实现代码如下：

import heapq

def dfs(u, parent, graph, subtree_size, subtree_weight):
    size = 1
    weight = 0
    for v, w in graph[u]:
        if v != parent:
            sz, wt = dfs(v, u, graph, subtree_size, subtree_weight)
            size += sz
            weight += wt
    subtree_size[u] = size
    subtree_weight[u] = weight + size

    return size, weight

def split_graph(graph, q):
    n = len(graph)
    subtree_size = [0] * n
    subtree_weight = [0] * n

    dfs(0, -1, graph, subtree_size, subtree_weight)

    heap = []
    for u in range(n):
        heapq.heappush(heap, (subtree_size[u], u))

    splits = []
    for i in range(q-1):
        _, u = heapq.heappop(heap)
        splits.append(u)

    splits.sort()

    components = []
    start = 0
    for u in splits:
        end = subtree_weight[u]
        components.append(graph[start:end])
        start = end

    components.append(graph[start:])
    
    return components

其中，graph是一个邻接表，表示图中每个顶点的相邻顶点和对应的边权重。例如，graph[u]表示与顶点u相邻的所有顶点和对应的边权重，以元组的形式存储。q表示需要分割的连通分支数。函数返回一个列表，包含q个连通分支，每个连通分支用邻接表表示。