python 二分图最大匹配代码

Python中可以使用网络流算法来求解二分图的最匹配问题，其中常用的算法是匈牙利算法。以下是一个简单的Python代码示例：

class BipartiteGraph:
    def __init__(self, graph):
        self.graph = graph
        self.m = len(graph)
        self.n = len(graph[0])
        self.match = [-1] * self.n

    def dfs(self, u, visited):
        for v in range(self.n):
            if self.graph[u][v] and not visited[v]:
                visited[v] = True
                if self.match[v] == -1 or self.dfs(self.match[v], visited):
                    self.match[v] = u
                    return True
        return False

    def max_matching(self):
        result = 0
        for u in range(self.m):
            visited = [False] * self.n
            if self.dfs(u, visited):
                result += 1
        return result


# 示例使用
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [0, 1, 0, 1],
         [0, 0, 1, 0]]

bipartite_graph = BipartiteGraph(graph)
max_matching = bipartite_graph.max_matching()
print("最大匹配数:", max_matching)

这段代码定义了一个`BipartiteGraph`类，其中`graph`参数是一个二维列表，表示二分图的邻接矩阵。`max_matching`方法使用匈牙利算法来计算最大匹配数。