Python中使用最大权匹配算法解决二分图最大权匹配问题

# 构建二分图，用矩阵表示。这里假设有 n 个顶点，前 n/2 个为左侧顶点，后 n/2 个为右侧顶点。
# 其中每个顶点的权值为 weights[i]。
n = 8
weights = [2, 1, 3, 2, 3, 4, 1, 2]
graph = [[0] * n for _ in range(n)]
for i in range(n//2):
    for j in range(n//2, n):
        graph[i][j] = weights[i] + weights[j]

# 最大权匹配算法，返回最大权匹配的权值之和。
def maximum_weight_matching(graph):
    n = len(graph)
    matching = [-1] * n
    while True:
        visited = [False] * n
        found = False
        for i in range(n):
            if matching[i] == -1:
                found |= dfs(i, graph, matching, visited)
        if not found:
            break
    return sum(graph[i][matching[i]] for i in range(n) if matching[i] != -1)

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

# 测试
print(maximum_weight_matching(graph))  # 输出 12