🧠 核心思路与关键步骤

我们可以将每一种配对方案看作二维平面上的一个点 (∑A, ∑B)，我们的目标就是找到一个点，使得其坐标的乘积 x * y 最小。

这个问题主要有两个难点：一是如何高效地找到这些可能的点，二是如何避免枚举所有情况（因为70!的枚举量是不可行的）。

1. 问题转化与算法选择

• 这是一个二分图完美匹配问题，但目标函数是两个和的乘积，而非单一权重。
• 借鉴最小乘积生成树的思想，我们可以利用分治策略，结合计算几何中的向量叉积来寻找可能的最优解。
• 使用KM算法（Kuhn-Munkres算法）来求解带权二分图的最小权完美匹配。需要注意的是，KM算法通常用于求最大权匹配，但通过权值取反，我们可以将其用于求解最小权匹配。

2. 算法流程

整个算法的核心流程可以通过下面的流程图来概览，它清晰地展示了分治与KM算法是如何协作的：

flowchart TD
    A[开始: 寻找初始点A<br>∑A最小, ∑B对应] --> B[寻找初始点B<br>∑B最小, ∑A对应]
    B --> C{递归分治<br>处理线段AB}
    C --> D[在AB左侧找点C<br>使△ABC面积最大<br>KM计算新权值]
    D --> E{找到点C?<br>且C在AB左侧?}
    E --是--> F[更新答案<br>递归处理AC]
    F --> G[递归处理CB]
    G --> C
    E --否--> H[递归结束]

下面我们来详细解释图中的几个关键步骤：

• 寻找初始点：首先，我们找到两个特殊的初始点：

  • 点A：∑A最小的匹配方案。通过将边权设置为Aᵢⱼ，运行KM算法得到。
  • 点B：∑B最小的匹配方案。通过将边权设置为Bᵢⱼ，运行KM算法得到。 这两个点通常位于"代价平面"的两端。

• 分治寻找更优点：在点A和点B确定的线段AB的左侧（从A指向B的向量左侧），寻找一个离该线段最远的点C。根据计算几何知识，点C使得三角形ABC的面积最大，此时点C离直线AB最远。

  • KM的新权值：为了找到这个点C，我们需要将匹配的边权设置为一个与向量叉积相关的值：(B.x - A.x) * Bᵢⱼ + (A.y - B.y) * Aᵢⱼ。运行KM算法求解这个新的最小权匹配，得到的点就是点C。
  • 递归分治：如果找到了这样的点C，并且它在AB的左侧（通过向量叉积判断），我们就用点C更新答案，并递归地在线段AC和线段CB上重复这个过程。如果点C不在AB左侧（叉积≥0），说明该区域没有更优解，递归终止。

3. 复杂度分析

• 每次递归调用需要进行一次KM算法，KM算法的时间复杂度为O(N³)。
• 分治的递归深度不会太深，因为点集的大小是有限的。总的复杂度在N≤70时是完全可以接受的。

💻 代码实现提示

1. KM算法实现：需要实现一个稳定的KM算法来求解最小权完美匹配。注意处理权值取反以及 slack 优化等细节。
2. 递归终止条件：当无法找到新的点C，或者点C不在线段AB左侧时，递归终止。
3. 答案更新：在递归过程中，不断计算当前找到的点的坐标乘积 (∑A * ∑B)，并更新最小值。

💎 总结

这道题的关键在于将抽象的乘积最小化问题，转化为二维平面上的点搜索问题，并巧妙地运用分治思想和KM算法，避免了暴力枚举。计算几何中向量叉积的应用是寻找潜在最优点的精髓。