最小费用最大流

import heapq

def dijkstra(graph, capacity, cost, source, sink):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    pq = [(0, source)]
    parent = [-1] * n
    flow = [0] * n
    
    while pq:
        d, u = heapq.heappop(pq)
        if u == sink:
            break
        for v, cap, c in graph[u]:
            if cap > flow[v] and dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                parent[v] = u
                flow[v] = min(cap - flow[v], flow[u])
                heapq.heappush(pq, (dist[v], v))
    
    return flow, parent

def min_cost_max_flow(graph, capacity, cost, source, sink):
    max_flow = 0
    min_cost = 0
    flow, parent = dijkstra(graph, capacity, cost, source, sink)
    
    while flow[sink] > 0:
        max_flow += flow[sink]
        v = sink
        while v != source:
            u = parent[v]
            min_cost += flow[sink] * cost[u][v]
            capacity[u][v] -= flow[sink]
            capacity[v][u] += flow[sink]
            v = u
        flow, parent = dijkstra(graph, capacity, cost, source, sink)
    
    return max_flow, min_cost

# Example usage
n = 4
graph = [
    [(1, 3, 2), (2, 2, 1)],
    [(2, 2, 1), (3, 3, 3)],
    [(3, 2, 2)],
    []
]
capacity = [[0, 3, 2, 0],
            [0, 0, 2, 3],
            [0, 0, 0, 2],
            [0, 0, 0, 0]]
cost = [[0, 2, 1, 0],
        [0, 0, 1, 3],
        [0, 0, 0, 2],
        [0, 0, 0, 0]]
source = 0
sink = 3

max_flow, min_cost = min_cost_max_flow(graph, capacity, cost, source, sink)
print("Max Flow:", max_flow)
print("Min Cost:", min_cost)