413.运动员最佳匹配问题

算法思路

1. 问题分析

本题属于二分图最大权匹配问题，需要将 n 个男运动员与 n 个女运动员配对，使得配对组合的总竞赛优势（P[i][j] × Q[j][i]）最大化。核心挑战在于：

• 建立男运动员（左侧点）和女运动员（右侧点）的带权二分图
• 求解最大权完美匹配
• 满足 n ≤ 20 的约束条件

2. 解决策略

采用 KM算法（Kuhn-Munkres算法）解决：

1. 权重矩阵构建：计算男 i 与女 j 配对的边权 a[i][j] = P[i][j] × Q[j][i]
2. 顶标初始化：设置左侧点顶标 lx[i] = max(a[i][j])，右侧点顶标 ly[j] = 0
3. DFS匹配过程：
   • 通过 DFS 寻找增广路径
   • 若无法匹配，计算最小调整量 minz
   • 调整顶标：lx[访问点] -= minz，ly[访问点] += minz
4. 重复匹配：对每个左侧点循环上述过程直到找到完美匹配
5. 结果计算：累加所有匹配边的权重

3. 复杂度分析

• 时间复杂度：O(n³)
  • 外层循环 n 个左侧点
  • 每个左侧点最多调整 n 次顶标
  • 每次 DFS 耗时 O(n)
• 空间复杂度：O(n²)
  • 存储 n×n 的权重矩阵
  • 辅助数组（lx, ly, visx, visy, pi）占用 O(n)

---

代码实现

C++解法

cpp
复制
1#include <iostream>
2#include <cstring>
3#include <climits>
4using namespace std;
5
6const int MAXN = 25;
7int a[MAXN][MAXN];   // 边权矩阵：a[i][j] = P[i][j] * Q[j][i]
8int lx[MAXN], ly[MAXN];  // 左右顶标
9int visx[MAXN], visy[MAXN];  // DFS访问标记
10int pi[MAXN];  // 匹配关系：pi[j]=i 表示女j匹配男i
11int n;
12
13// DFS寻找增广路径
14bool dfs(int u) {
15    visx[u] = 1;  // 标记左侧点u已访问
16    for (int v = 1; v <= n; v++) {
17        if (!visy[v]) {  // 右侧点v未被访问
18            int gap = lx[u] + ly[v] - a[u][v];  // 计算顶标间隙
19            if (gap == 0) {  // 符合相等子图条件
20                visy[v] = 1;  // 标记右侧点v
21                // 若v未匹配或已匹配点可调整
22                if (pi[v] == 0 || dfs(pi[v])) {  // O(n)递归
23                    pi[v] = u;  // 建立匹配关系
24                    return true;
25                }
26            } 
27            // 记录最小调整量（正间隙）
28            else if (gap > 0) {
29                minz = min(minz, gap);  // 更新全局最小值
30            }
31        }
32    }
33    return false;
34}
35
36// KM算法主过程
37void km() {
38    for (int i = 1; i <= n; i++) {
39        while (true) {
40            minz = INT_MAX;  // 初始化最小调整量
41            memset(visx, 0, sizeof(visx));  // 重置访问标记
42            memset(visy, 0, sizeof(visy));
43            if (dfs(i)) break;  // 找到增广路径则跳出
44            
45            // 调整顶标：访问过的左侧点减minz，右侧点加minz
46            for (int j = 1; j <= n; j++) {
47                if (visx[j]) lx[j] -= minz;  // 左侧顶标调整
48            }
49            for (int j = 1; j <= n; j++) {
50                if (visy[j]) ly[j] += minz;  // 右侧顶标调整
51            }
52        }
53    }
54}
55
56int main() {
57    // 输入处理
58    cin >> n;
59    // 读取P矩阵
60    for (int i = 1; i <= n; i++) {
61        for (int j = 1; j <= n; j++) {
62            cin >> a[i][j];
63        }
64    }
65    // 读取Q矩阵并计算边权
66    for (int i = 1; i <= n; i++) {
67        for (int j = 1; j <= n; j++) {
68            int q_val;
69            cin >> q_val;
70            a[j][i] *= q_val;  // 注意下标：Q[j][i]对应a[j][i]
71        }
72    }
73    
74    // 初始化左侧顶标
75    for (int i = 1; i <= n; i++) {
76        for (int j = 1; j <= n; j++) {
77            lx[i] = max(lx[i], a[i][j]);  // O(n²)初始化
78        }
79    }
80    
81    // 执行KM算法
82    km();
83    
84    // 计算结果
85    int ans = 0;
86    for (int i = 1; i <= n; i++) {
87        ans += a[pi[i]][i];  // 累加匹配边权
88    }
89    cout << ans;
90    return 0;
91}

代码解释：

1. 函数参数说明
   • dfs(u)：从左侧点 u 寻找增广路径
   • km()：KM算法主流程，为每个左侧点寻找匹配
2. 核心逻辑解析
   • 权重计算：a[j][i] *= q_val 实现 P[i][j]×Q[j][i]
   • 顶标初始化：lx[i] 取男 i 的最大边权
   • DFS匹配：通过调整顶标逐步扩大相等子图
   • 结果累加：遍历 pi 数组求和匹配边权
3. 特殊处理
   • 边界条件：minz = INT_MAX 确保首次比较有效
   • 下标对齐：矩阵存储从 1 开始，匹配题目描述

Python3解法

python
复制
1def main():
2    import sys
3    sys.setrecursionlimit(10000)  # 防止DFS递归深度过大
4    
5    n = int(sys.stdin.readline())
6    a = [[0] * (n + 1) for _ in range(n + 1)]  # 边权矩阵(1-indexed)
7    p = []  # 存储P矩阵
8    q = []  # 存储Q矩阵
9    
10    # 读取P矩阵
11    for _ in range(n):
12        p.append(list(map(int, sys.stdin.readline().split())))
13    
14    # 读取Q矩阵
15    for _ in range(n):
16        q.append(list(map(int, sys.stdin.readline().split())))
17    
18    # 构建边权矩阵 a[i][j] = P[i-1][j-1] * Q[j-1][i-1]
19    for i in range(n):
20        for j in range(n):
21            # 注意下标转换：P的行i对应a的行i+1，Q的行j对应a的列i+1
22            a[i + 1][j + 1] = p[i][j] * q[j][i]  # 关键计算
23    
24    # 初始化顶标
25    lx = [0] * (n + 1)  # 左侧顶标
26    ly = [0] * (n + 1)  # 右侧顶标
27    pi = [0] * (n + 1)  # 匹配关系 pi[j]=i
28    
29    # 设置左侧顶标初始值
30    for i in range(1, n + 1):
31        lx[i] = max(a[i][1:])  # 取第i行最大值
32    
33    # DFS寻找增广路径
34    def dfs(u):
35        nonlocal minz  # 声明使用外层minz变量
36        visx[u] = 1
37        for v in range(1, n + 1):
38            if not visy[v]:
39                gap = lx[u] + ly[v] - a[u][v]
40                if gap == 0:  # 满足相等子图条件
41                    visy[v] = 1
42                    if pi[v] == 0 or dfs(pi[v]):  # 递归查找
43                        pi[v] = u
44                        return True
45                elif gap > 0:
46                    minz = min(minz, gap)  # 更新最小调整量
47        return False
48    
49    # KM主算法
50    for i in range(1, n + 1):
51        while True:
52            minz = float('inf')
53            visx = [0] * (n + 1)  # 重置访问标记
54            visy = [0] * (n + 1)
55            if dfs(i):
56                break
57            # 调整顶标
58            for j in range(1, n + 1):
59                if visx[j]:
60                    lx[j] -= minz
61            for j in range(1, n + 1):
62                if visy[j]:
63                    ly[j] += minz
64    
65    # 计算结果
66    ans = 0
67    for j in range(1, n + 1):
68        ans += a[pi[j]][j]  # 累加匹配边权
69    print(ans)
70
71if __name__ == '__main__':
72    main()

代码解释：

1. 与C++实现的差异
   • 下标处理：Python使用1-indexed矩阵避免边界检查
   • 递归深度：sys.setrecursionlimit 解决DFS递归限制
   • 全局变量：nonlocal minz 替代C++的全局变量
2. Python特性应用
   • 列表推导：初始化二维矩阵 a = [[0]*(n+1) for ...]
   • 动态类型：直接使用 float('inf') 表示无穷大
   • 切片操作：max(a[i][1:]) 快速取行最大值
3. 关键逻辑解析
   • 边权计算：a[i+1][j+1] = p[i][j] * q[j][i] 实现题目公式
   • 顶标调整：动态修改 lx/ly 扩大相等子图范围
   • 结果累加：通过 pi 数组反向索引匹配边

---

复杂度对比

选择建议：

1. 首选C++：当 n 接近上限(20)或需要极致性能时
2. 首选Python：当需要快速验证算法或 n 较小时
3. 注意点：Python需设置递归深度 sys.setrecursionlimit