python
def hungarian(cost):
"""
求最小成本指派。
要求：至少有一行，矩阵非空且为矩形，行数 <= 列数。
返回：(每行匹配的列索引列表, 最小总成本)
"""
n = len(cost)
if n == 0 or not cost[0]:
raise ValueError("成本矩阵不能是空的")
m = len(cost[0])
if any(len(row) != m for row in cost):
raise ValueError("成本矩阵必须是矩形")
if n > m:
raise ValueError("此实现要求行数不大于列数")
u = [0] * (n + 1)
v = [0] * (m + 1)
p = [0] * (m + 1)
way = [0] * (m + 1)
for i in range(1, n + 1):
p[0] = i
j0 = 0
minv = [float("inf")] * (m + 1)
used = [False] * (m + 1)
while True:
used[j0] = True
i0 = p[j0]
delta = float("inf")
j1 = 0
for j in range(1, m + 1):
if not used[j]:
cur = cost[i0-1][j-1] - u[i0] - v[j]
if cur < minv[j]:
minv[j] = cur
way[j] = j0
if minv[j] < delta:
delta = minv[j]
j1 = j
for j in range(m + 1):
if used[j]:
u[p[j]] += delta
v[j] -= delta
else:
minv[j] -= delta
j0 = j1
if p[j0] == 0:
break
while True:
j1 = way[j0]
p[j0] = p[j1]
j0 = j1
if j0 == 0:
break
assignment = [0] * n
for j in range(1, m + 1):
if p[j] != 0:
assignment[p[j] - 1] = j - 1
total = sum(
cost[i][assignment[i]]
for i in range(n)
)
return assignment, total
cost = [
[4, 1, 3],
[2, 0, 5],
[3, 2, 2]
]
assignment, total = hungarian(cost)
workers = ["甲", "乙", "丙"]
jobs = ["A", "B", "C"]
for i, j in enumerate(assignment):
print(
workers[i],
"负责任务",
jobs[j],
"成本",
cost[i][j]
)
print("最小总成本:", total)
python
import numpy as np
from scipy.optimize import linear_sum_assignment
cost = np.array([
[4, 1, 3],
[2, 0, 5],
[3, 2, 2]
])
rows, cols = linear_sum_assignment(cost)
print("工人索引:", rows)
print("任务索引:", cols)
print("最小成本:", cost[rows, cols].sum())