用Python实现树形网络流算法

# 定义节点类
class Node:
    def __init__(self, id):
        self.id = id
        self.parent = None
        self.children = []

    def add_child(self, child):
        self.children.append(child)
        child.parent = self

    def is_leaf(self):
        return len(self.children) == 0

    def is_root(self):
        return self.parent is None

# 定义树形网络流算法类
class TreeNetworkFlow:
    def __init__(self, n):
        self.n = n
        self.nodes = [None] + [Node(i) for i in range(1, n+1)]  # 为方便计算，将节点下标从1开始编号
        self.capacity = [[0] * (n+1) for _ in range(n+1)]
        self.flow = [[0] * (n+1) for _ in range(n+1)]

    def add_edge(self, u, v, cap):
        self.capacity[u][v] = cap

    def maxflow(self, s, t):
        # 构建分层图
        levels = [-1] * (self.n+1)
        queue = [s]
        levels[s] = 0
        while queue:
            u = queue.pop(0)
            for v in range(1, self.n+1):
                if levels[v] < 0 and self.capacity[u][v] > self.flow[u][v]:
                    levels[v] = levels[u] + 1
                    queue.append(v)

        # 如果汇点不可达，则退出
        if levels[t] < 0:
            return 0

        # 找到增广路并更新流量
        def dfs(u, t, f):
            if u == t:
                return f
            for v in self.nodes[u].children:
                if levels[v.id] == levels[u] + 1 and self.capacity[u][v.id] > self.flow[u][v.id]:
                    df = dfs(v.id, t, min(f, self.capacity[u][v.id] - self.flow[u][v.id]))
                    if df > 0:
                        self.flow[u][v.id] += df
                        self.flow[v.id][u] -= df
                        return df
            return 0

        res = 0
        while True:
            df = dfs(s, t, float("inf"))
            if df == 0:
                break
            res += df

        return res

# 示例代码
tnf = TreeNetworkFlow(6)
tnf.add_edge(1, 2, 10)
tnf.add_edge(1, 3, 10)
tnf.add_edge(2, 4, 10)
tnf.add_edge(2, 5, 10)
tnf.add_edge(3, 6, 10)
print(tnf.maxflow(1, 6))  # 输出10