匈牙利算法python

匈牙利算法是一种用于求解二分图最大匹配的算法，以下是Python实现：

class HungarianAlgorithm:
    def __init__(self, graph):
        self.graph = graph
        self.n = len(graph)
        self.mate = [-1] * self.n

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

    def max_matching(self):
        match = 0
        for i in range(self.n):
            seen = [False] * self.n
            if self.dfs(i, seen):
                match += 1
        return match

其中，`graph`是一个二维数组，表示二分图的邻接矩阵。`mate`数组表示每个右侧节点匹配到的左侧节点的编号，初始值为-1。`dfs`函数用于查找增广路径，如果找到了增广路径则返回True，否则返回False。`max_matching`函数用于求解最大匹配，遍历所有左侧节点，对于每个节点都运行一次`dfs`函数查找增广路径，如果找到了则将匹配数加1。最终返回匹配数即可。