输入:第一行读入两个整数 m,n。 m表示女孩个数, n 表示男孩个数。 第二行有 m个数,表示 m个女孩的身高。 第三行有 n个数,表示 n个男孩的身高。
时间: 2024-02-25 17:56:38 浏览: 47
好的,那么接下来我会给出代码实现,假设你已经将输入读入到如下变量中:
```python
m = 3
n = 4
girl_heights = [165, 170, 175]
boy_heights = [170, 172, 173, 180]
```
那么可以使用以下代码实现匹配过程:
```python
import math
def abs_diff(x, y):
return abs(x - y)
def hungarian(g, n, m):
# 初始化匹配数组
match = [-1] * m
# 寻找增广路径的函数
def dfs(u, vis):
for v in range(m):
if not vis[v] and g[u][v]:
vis[v] = True
if match[v] == -1 or dfs(match[v], vis):
match[v] = u
return True
return False
# 匹配过程
for i in range(n):
# 初始化访问数组
vis = [False] * m
# 寻找增广路径
dfs(i, vis)
# 计算匹配值
ans = 0
for i in range(n):
ans += abs_diff(boy_heights[i], girl_heights[match[i]])
return ans
# 构建二分图
g = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
g[i][j] = abs_diff(boy_heights[i], girl_heights[j])
# 求所有男孩匹配值和的最小值
min_match_value = hungarian(g, n, m)
print(min_match_value) # 输出结果为 3,即男孩 0 匹配女孩 1,男孩 1 匹配女孩 0,男孩 2 匹配女孩 2,匹配值和为 3
```
希望这个例子可以帮助你理解匈牙利算法的实现过程。
阅读全文