匈牙利算法代码

以下是一个简单的匈牙利算法的 Python 代码实现：

class BipartiteGraph:
    def __init__(self, graph):
        self.graph = graph
        self.m = len(graph[0])
        self.n = len(graph)
        
    def bpm(self, u, matchR, seen):
        for v in range(self.m):
            if self.graph[u][v] and not seen[v]:
                seen[v] = True
                if matchR[v] == -1 or self.bpm(matchR[v], matchR, seen):
                    matchR[v] = u
                    return True
        return False
    
    def max_matching(self):
        matchR = [-1] * self.m
        result = 0
        for i in range(self.n):
            seen = [False] * self.m
            if self.bpm(i, matchR, seen):
                result += 1
        return result

其中，`graph` 表示二分图的邻接矩阵，`n` 和 `m` 分别表示左侧和右侧顶点的数量。`bpm` 方法是核心的递归函数，用于寻找增光路径。`max_matching` 方法是外部的接口，用于计算最大匹配数。