匈牙利算法求解运输问题代码

以下是使用匈牙利算法求解最小费用最大流运输问题的 Python 代码示例：

INF = float('inf')

class Hungarian:
    def __init__(self, n):
        self.n = n
        self.w = [[0] * n for _ in range(n)]
        self.match = [-1] * n
    
    def add_edge(self, u, v, cost):
        self.w[u][v] = cost
    
    def bfs(self, s, t, prev, vis):
        que = []
        que.append(s)
        vis[s] = True
        while que:
            u = que.pop(0)
            for v in range(self.n):
                if not vis[v] and self.w[u][v] > 0:
                    vis[v] = True
                    prev[v] = u
                    if v == t:
                        return True
                    que.append(v)
        return False
    
    def min_cost_max_flow(self, s, t):
        flow = 0
        cost = 0
        while True:
            vis = [False] * self.n
            prev = [-1] * self.n
            if not self.bfs(s, t, prev, vis):
                break
            f = INF
            v = t
            while v != s:
                u = prev[v]
                f = min(f, self.w[u][v])
                v = u
            flow += f
            cost += f * self.w[prev[t]][t]
            v = t
            while v != s:
                u = prev[v]
                self.w[u][v] -= f
                self.w[v][u] += f
                v = u
        return flow, cost

    def match_cost(self):
        res = 0
        for i in range(self.n):
            if self.match[i] != -1:
                res += self.w[self.match[i]][i]
        return res

    def match_edges(self):
        edges = []
        for i in range(self.n):
            if self.match[i] != -1:
                edges.append((self.match[i], i))
        return edges
    
    def max_matching(self):
        for i in range(self.n):
            for j in range(self.n):
                self.w[i][j] = -self.w[i][j]
        for i in range(self.n):
            self.w[i][i] = -INF
        self.match = [-1] * self.n
        for i in range(self.n):
            q = [(-self.w[i][j], j) for j in range(self.n)]
            heapq.heapify(q)
            vis = [False] * self.n
            vis[i] = True
            while q:
                cost, j = heapq.heappop(q)
                if vis[j]:
                    continue
                vis[j] = True
                if self.match[j] == -1 or -self.w[self.match[j]][j] > cost:
                    self.match[j] = i
                    self.w[i][j] = -cost
                    break
        return sum(self.w[i][self.match[i]] for i in range(self.n)), self.match

其中，`self.w` 是邻接矩阵表示的图，`self.match` 是匹配数组，初始值为 -1，表示未匹配。`add_edge` 方法用于添加边。`min_cost_max_flow` 方法用于求解最小费用最大流，返回最大流和最小费用。`match_cost` 方法用于返回匹配的总费用，`match_edges` 方法用于返回匹配的边。`max_matching` 方法用于求解最大匹配，返回最大匹配和匹配数组。