运动员最佳匹配问题

问题前面就不多说，简单模拟得到矩阵。

然后对矩阵用匈牙利得到最小匹配。

我累了，看代码吧

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;
int n;
int P[MAXN][MAXN], Q[MAXN][MAXN];
int cost[MAXN][MAXN];
int u[MAXN], v[MAXN], p[MAXN], way[MAXN];

int hungarian() {
    for (int i = 1; i <= n; i++) {
        p[0] = i;
        int j0 = 0;
        vector<int> minv(n+1, INT_MAX);
        vector<bool> used(n+1, false);
        do {
            used[j0] = true;
            int i0 = p[j0], delta = INT_MAX, j1 = 0;
            for (int j = 1; j <= n; j++) {
                if (!used[j]) {
                    int cur = -cost[i0][j] - u[i0] - v[j]; // 取负数求最大匹配
                    if (cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if (minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for (int j = 0; j <= n; j++) {
                if (used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while (p[j0] != 0);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0);
    }

    int result = 0;
    for (int j = 1; j <= n; j++) result += cost[p[j]][j];
    return result;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> P[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> Q[i][j];
    // 构造竞赛优势矩阵
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cost[i+1][j+1] = P[i][j] * Q[j][i];
    cout << hungarian() << endl;
    return 0;
}