题解思路

问题分析

我们需要将 $n$ 个男生和 $n$ 个女生配对，使得：

最大，其中 $a_i$ 和 $b_i$ 分别是每对舞伴的喜悦程度和不协调程度。

这是一个典型的0-1分数规划问题。

关键思路：分数规划

分数规划的核心思想是：将分式优化问题转化为线性优化问题。

对于目标函数：

我们可以通过二分答案来求解。

算法框架

1. 二分答案

假设我们猜测最大值为 $mid$，那么需要判断是否存在一种配对方案使得：

等价于：

2. 权重重构

对于每一对可能的配对 $(i,j)$，定义新权重：

现在问题转化为：是否存在完美匹配使得新权重的总和 $\geq 0$。

3. 匹配判定

这是一个二分图最大权完美匹配问题：

• 左边：$n$ 个男生
• 右边：$n$ 个女生
• 边权：$w_{ij} = a_{ij} - mid \cdot b_{ij}$

如果最大权完美匹配的权重和 $\geq 0$，说明 $mid$ 可行，可以尝试更大的值；否则需要减小 $mid$。

匹配算法选择

对于二分图最大权完美匹配，常用的算法有：

1. KM算法（Kuhn-Munkres）

• 时间复杂度：$O(n^3)$
• 适用于稠密图
• 对于 $n \leq 100$ 完全可行

2. 最小费用最大流

• 也可以解决，但KM算法更直接

边界情况

1. 起点就是终点：如果初始就在出口，移动次数为0
2. 无法到达：BFS结束后仍未到达终点，返回-1
3. 精度问题：浮点数比较要小心，使用相对误差或绝对误差

实现细节

1. 权重处理：注意 $w_{ij}$ 可能是负数
2. KM算法：需要正确处理顶标调整
3. 二分边界：根据数据范围 $a_{ij}, b_{ij} \leq 10^4$，$C$ 的最大值不会超过 $10^4$

样例分析

对于样例：

n=3
a = [[19,17,16],[25,24,23],[35,36,31]]
b = [[9,5,6],[3,4,2],[7,8,9]]

通过分数规划求得最优值 $5.357143$。

总结

这道题是分数规划的经典应用：

1. 问题识别：分式目标函数 → 分数规划
2. 算法选择：二分答案 + 二分图最大权匹配
3. 实现要点：KM算法 + 精度控制
4. 复杂度：$O(n^3 \log(\frac{1}{\epsilon}))$ 可接受

分数规划的思想可以推广到很多类似的问题：当目标函数是分式形式时，都可以考虑通过二分答案将其转化为线性问题。