题目分析

这道题目是关于稳定婚姻问题的变种，要求我们找到最优的雇员与主管的匹配方案，使得所有人的满意度总和最高。具体来说：

1. 输入：

   • 多个测试用例，每个测试用例包含N个主管和N个雇员。
   • 每个主管对雇员的排名（1表示最喜欢，N表示最不喜欢）。
   • 每个雇员对主管的排名（同样1表示最喜欢，N表示最不喜欢）。

2. 输出：

   • 最佳匹配的平均差异值（保留6位小数）。
   • 所有可能的最佳匹配方案（按升序排列）。
   • 每个匹配方案中，主管与雇员的对应关系。

解题思路

1. 问题建模：

   • 将主管和雇员看作二分图的两部分。
   • 使用KM算法（Kuhn-Munkres算法）来解决带权二分图的最大权匹配问题。

2. 权值计算：

   • 对于主管i和雇员j，计算匹配的权值：Map[i][j] = (N - supervisor_rank) + (N - employee_rank)。
   • 这样，权值越大表示匹配的满意度越高。

3. KM算法：

   • 初始化顶标lx和ly。
   • 使用DFS寻找增广路，调整顶标直到找到完美匹配。
   • 计算最大权匹配的总权值。

4. 输出结果：

   • 计算平均差异值：(2N - total_weight) / (2N)。
   • 回溯所有可能的匹配方案，输出权值等于最大权值的所有匹配。

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int Map[20][20], n;
int link[20], vis[20], cnt;
int lx[20], ly[20];
int s[20], t[20], ans;

int dfs(int u) {
    s[u] = 1;
    for(int i = 1; i <= n; i++) {
        if(!t[i] && lx[u] + ly[i] == Map[u][i]) {
            t[i] = 1;
            if(link[i] == -1 || dfs(link[i])) {
                link[i] = u;
                return 1;
            }
        }
    }
    return 0;
}

void out(int dept, int temp) {
    if(temp > ans) return;
    if(dept > n) {
        if(temp != ans) return;
        printf("Best Pairing %d\n", ++cnt);
        for(int i = 1; i <= n; i++)
            printf("Supervisor %d with Employee %d\n", i, link[i]);
        return;
    } else {
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            vis[i] = 1;
            link[dept] = i;
            out(dept + 1, temp - Map[dept][i]);
            vis[i] = 0;
        }
    }
}

int main() {
    int N, step = 0, i, j, x, min1, k;
    scanf("%d", &N);
    while(N--) {
        memset(Map, 0, sizeof(Map));
        scanf("%d", &n);
        // 读取主管对雇员的排名
        for(i = 1; i <= n; i++)
            for(j = n; j >= 1; j--)
                scanf("%d", &x), Map[x][i] += j - n;
        // 读取雇员对主管的排名
        for(i = 1; i <= n; i++)
            for(j = n; j >= 1; j--)
                scanf("%d", &x), Map[i][x] += j - n;
        // 初始化顶标
        for(i = 1; i <= n; i++) {
            lx[i] = -100;
            ly[i] = 0;
            for(j = 1; j <= n; j++)
                lx[i] = max(lx[i], Map[i][j]);
        }
        memset(link, -1, sizeof(link));
        // KM算法主循环
        for(k = 1; k <= n; k++) {
            while(1) {
                memset(s, 0, sizeof(s));
                memset(t, 0, sizeof(t));
                if(dfs(k)) break;
                min1 = 100;
                for(i = 1; i <= n; i++) {
                    if(!s[i]) continue;
                    for(j = 1; j <= n; j++) {
                        if(t[j]) continue;
                        min1 = min(min1, lx[i] + ly[j] - Map[i][j]);
                    }
                }
                for(i = 1; i <= n; i++) {
                    if(s[i]) lx[i] -= min1;
                    if(t[i]) ly[i] += min1;
                }
            }
        }
        // 计算最大权值
        for(i = 1, ans = 0; i <= n; i++)
            if(link[i] > 0)
                ans -= Map[link[i]][i];
        printf("Data Set %d, Best average difference: %.6f\n", ++step, 0.5 * ans / n);
        cnt = 0;
        memset(vis, 0, sizeof(vis));
        out(1, 0);
        printf("\n");
    }
    return 0;
}

代码说明

1. 输入处理：

   • 读取测试用例数量N。
   • 对于每个测试用例，读取主管和雇员的排名，并计算匹配权值Map[i][j]。

2. KM算法：

   • 初始化顶标lx和ly。
   • 使用DFS寻找增广路，调整顶标直到找到完美匹配。
   • 计算最大权匹配的总权值。

3. 输出结果：

   • 计算平均差异值并输出。
   • 回溯所有可能的匹配方案，输出权值等于最大权值的所有匹配。