用 Python 实现最小费用最大流算法：求解带权网络流问题

import heapq

class Edge:
    def __init__(self, u, v, w, c):
        self.u = u
        self.v = v
        self.w = w
        self.c = c
        self.next = None

class Graph:
    def __init__(self, n):
        self.n = n
        self.head = [None] * (n + 1)
        self.dist = [0] * (n + 1)
        self.prev = [-1] * (n + 1)
        self.visited = [False] * (n + 1)

    def add_edge(self, u, v, w, c):
        edge = Edge(u, v, w, c)
        edge.next = self.head[u]
        self.head[u] = edge

    def clear(self):
        self.dist = [0] * (self.n + 1)
        self.prev = [-1] * (self.n + 1)
        self.visited = [False] * (self.n + 1)

    def dijkstra(self, s, t):
        self.clear()
        pq = []
        heapq.heappush(pq, (0, s))
        while pq:
            (d, u) = heapq.heappop(pq)
            if self.visited[u]:
                continue
            self.visited[u] = True
            p = self.head[u]
            while p:
                v = p.v
                w = p.w
                c = p.c
                if w > 0 and (self.prev[v] == -1 or self.dist[v] > self.dist[u] + c):
                    self.prev[v] = u
                    self.dist[v] = self.dist[u] + c
                    heapq.heappush(pq, (self.dist[v], v))
                p = p.next
            if u == t:
                return True
        return False

    def min_cost_max_flow(self, s, t):
        max_flow = 0
        min_cost = 0
        while self.dijkstra(s, t):
            flow = float('inf')
            u = t
            while u != s:
                v = self.prev[u]
                p = self.head[v]
                while p.u != v:
                    p = p.next
                flow = min(flow, p.w)
                u = v
            u = t
            while u != s:
                v = self.prev[u]
                p = self.head[v]
                while p.u != v:
                    p = p.next
                p.w -= flow
                p = self.head[u]
                while p.u != v:
                    p = p.next
                p.w += flow
                u = v
            max_flow += flow
            min_cost += flow * self.dist[t]
        return (max_flow, min_cost)

# 测试代码
g = Graph(6)
g.add_edge(1, 2, 10, 2)
g.add_edge(1, 3, 10, 1)
g.add_edge(2, 3, 6, 6)
g.add_edge(2, 4, 5, 2)
g.add_edge(2, 5, 6, 3)
g.add_edge(3, 5, 4, 3)
g.add_edge(4, 6, 8, 6)
g.add_edge(5, 4, 6, 1)
g.add_edge(5, 6, 10, 9)
print(g.min_cost_max_flow(1, 6)) # 输出 (10, 118)