最小树形图模板朱刘算法分享

最小树形图模板朱刘算法分享

最小树形图（Minimum Spanning Arborescence）是有向图的一种特殊的生成树，它包含了图中所有的点且仅有一个点入度为0（源点）。朱刘算法是一种求解最小树形图的算法，时间复杂度为$O(VE)$。

以下是朱刘算法的完整攻略：

1. 算法原理

朱刘算法基于”缩点”思想和“基环树”的性质，在每一个生成树已经连出来的点（包括源点）中选择一个代表进行缩点，每次将点进行缩点，并记缩点后连出去的边的最小边权作为这个点的代价，缩点后生成的新图上执行贪心算法来找到最小树形图。如果新图中存在环，就对环进行“缩环”，将环上的若干个点缩成一个点，重新生成一个新图，递归地执行缩点/缩环操作，直到得到一棵树为止。

2. 详细步骤

按照如下步骤执行朱刘算法：

构建一个新图 $G'$，其中新图的顶点与 $G$ 的强连通分量一一对应。
对强连通分量内部进行缩点。这个过程需要在线性时间内完成，并确定构建新图 $G'$ 后，对应的新源点。
对 $G'$ 执行普通的 Prim 或 Kruskal 算法。这两个算法都能在线性时间内找到 $G'$ 的最小生成树。
如果生成的最小树不包含新源点，算法结束。
如果生成的最小树包含新源点，则需要查找环。对于任意一条从新源点开始的出边 $(u,w)$，在缩点后的点集合中，找到 $(u,w)$ 所指向的顶点 $v$。如果 $v$ 已经在环中，则不需要再次寻找环。否则，从 $v$ 开始继续深度遍历，得到一个环，并从中选取一条基本边 e，再执行缩环操作
缩环后需要重新建图。对于原图 $G$ 中的每个顶点，找到新图 $G'$ 中所代表的强连通分量，把该顶点标记为这个分量的代表点，并把这个顶点所在的连通分量的所有边都放进一个集合里。
在这个新的图上，重复步骤3，直到找到一棵不包含新源点的最小生成树。

3. 算法实现

这里提供一个实现朱刘算法的Python代码示例：

import sys
from typing import List, Tuple

INF = sys.maxsize


def add_edge(u: int, v: int, w: int, adj: List[List[Tuple[int, int]]]) -> None:
    adj[u].append((v, w))


def update(son: List[int], delta: List[int], dad: List[int], x: int) -> None:
    delta[x] = INF
    for i in range(len(son)):
        y = son[i]
        if dad[y] == x:
            update(son, delta, dad, y)
            delta[x] = min(delta[x], delta[y])

        delta[x] = min(delta[x], delta[y] - INF)


def zhu_liu(n: int, root: int, edges: List[Tuple[int, int, int]]) -> Tuple[int, List[int]]:
    """zhu_liu algorithm

    Args:
        n (int): total number of vertices
        root (int): root of the minimum spanning arborescence
        edges (List[Tuple[int, int, int]]): edges of the graph, (u, v, w)

    Returns:
        Tuple[int, List[int]]: minimum cost and MST
    """
    m = len(edges)
    dad = [root for _ in range(n)]
    best = [INF for _ in range(n)]
    vis = [False for _ in range(n)]

    for _ in range(n):
        for j in range(m):
            u, v, w = edges[j]
            if best[v] > w and u != v:
                best[v] = w
                dad[v] = u

        for j in range(n):
            if j == root:
                continue
            if best[j] == INF:
                return -1, []
            update([j], best, dad, j)
            for k in range(len(edges)):
                u, v, w = edges[k]
                if dad[u] != u and best[v] == w:
                    dad[v] = u
                    break

        if dad[root] == root:
            return sum(best), dad

        cur = root
        next_ = root
        while vis[cur]:
            cur = dad[cur]
        while not vis[cur]:
            vis[cur] = True
            cur = dad[cur]
        for i in range(n):
            if vis[i]:
                best[i] -= best[cur]
                dad[i] = cur
            else:
                best[i] -= best[next_]

        root = next_

    return -1, []

4. 示例说明

以下是两个使用朱刘算法求解最小树形图的示例：

示例 1：

给定图 $G$，如下所示：

       1      6      7
   o ---> o ---> o ---> o
   | 4    /\     |    / |
2  |    /    \   |  /   |8
   v  /      \  v /    v
   o <---- o <--- o <--- o
      5      3      9

执行朱刘算法后，得到生成的最小树形图如下：

        6          7
    o ---> o ---> o
    |      /       |                  
   2|    /    8    |5  
    v  /          v           
    o <-----------o
         3

示例 2：