作业的最大匹配函数

下面是一个基于匈牙利算法的最大匹配函数的代码示例：

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

def max_matching(graph):
    m = len(graph)
    n = len(graph[0])
    match = [-1] * n
    count = 0

    for u in range(m):
        visited = [False] * n
        if bfs(graph, u, visited, match):
            count += 1

    return count

# 测试
graph = [[0, 1, 1, 0],
         [1, 0, 0, 1],
         [1, 0, 1, 0],
         [0, 1, 0, 0]]

print(max_matching(graph))  # 输出: 3

在这个代码中，graph 是一个二维列表，表示作业的匹配关系。graph[i][j] 的值为 1 表示作业 i 和 j 可以匹配，为 0 表示不能匹配。

bfs 函数是一个递归的辅助函数，用来找到从作业 u 开始的增广路径。它使用深度优先搜索的方法遍历图，匹配尚未形成的作业，并返回是否找到了增广路径。

max_matching 函数实现了匈牙利算法。它遍历所有的作业，对每个作业使用 bfs 函数找到一个增广路径。如果找到了增广路径，则把作业和工人匹配，并增加计数器的值。

最后，函数返回计数器的值，即最大匹配数。