题意分析

稳定婚姻问题是经典的博弈论问题，本题要求找到男性最优的稳定婚姻。具体来说：

• 有n个男性和n个女性，每个性别对另一性别的成员有偏好排序
• 稳定婚姻定义：不存在(m,f)使得f更喜欢m且m更喜欢f，而两人当前未配对
• 男性最优稳定婚姻：在所有稳定婚姻中，每个男性都能匹配到尽可能偏好的女性

输入包含男性和女性的偏好列表，需要输出按男性字典序排列的配对结果。

解题思路

核心算法：Gale-Shapley算法

该算法是解决稳定婚姻问题的经典方法，专门用于寻找男性最优的稳定婚姻，步骤如下：

1. 男性求婚：男性按偏好顺序向女性求婚
2. 女性选择：女性若未订婚，接受求婚；若已订婚，比较求婚者与当前伴侣，选择更偏好的一方
3. 迭代过程：未订婚的男性持续求婚，直到所有男性都订婚

算法步骤

1. 输入处理：读取男性和女性名字，存储男女偏好列表
2. 数据预处理：
   • 男性偏好列表ml[x][j]：男性x的第j偏好女性
   • 女性偏好排名rk[y][x]：女性y对男性x的偏好排名（数值越小越喜欢）
3. 求婚过程：使用队列维护未订婚男性，按偏好顺序求婚
4. 订婚处理：女性根据偏好选择更优的求婚者
5. 结果输出：按男性字典序输出配对结果

代码逻辑解析

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 40

int ml[Maxn][Maxn], rk[Maxn][Maxn];  // ml:男性偏好列表，rk:女性对男性的偏好排名
int fw[Maxn], fh[Maxn], nt[Maxn];    // fw:男性当前匹配的女性，fh:女性当前匹配的男性，nt:男性当前求婚进度

int n;
char s[Maxn];

queue<int> q;  // 存储未订婚的男性

// 初始化数据
void init() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%s", s);  // 读取男性和女性名字
    for (int i = 1; i <= n; i++) scanf("%s", s);
    
    while (!q.empty()) q.pop();
    memset(fw, 0, sizeof(fw));  // 男性当前无匹配
    memset(fh, 0, sizeof(fh));  // 女性当前无匹配
    
    // 读取男性偏好列表
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int x = s[0] - 'a' + 1;  // 男性编号(1~n)
        for (int j = 1; j <= n; j++) {
            int y = s[j+1] - 'A' + 1;  // 女性编号(1~n)
            ml[x][j] = y;  // 男性x的第j偏好是女性y
        }
        fw[x] = 0; nt[x] = 1;  // 男性x未订婚，下一次求婚是第1偏好
        q.push(x);  // 男性x进入求婚队列
    }
    
    // 读取女性偏好排名
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int x = s[0] - 'A' + 1;  // 女性编号(1~n)
        for (int j = 1; j <= n; j++) {
            int y = s[j+1] - 'a' + 1;  // 男性编号(1~n)
            rk[x][y] = j;  // 女性x对男性y的偏好排名为j（j越小越喜欢）
        }
        fh[x] = 0;  // 女性x未订婚
    }
}

// 处理订婚逻辑
void engage(int x, int y) {
    int z = fh[y];  // 女性y当前的未婚夫
    if (z) {  // 若女性y已订婚
        fw[z] = 0;  // 原未婚夫z恢复单身
        q.push(z);  // z重新进入求婚队列
    }
    fw[x] = y; fh[y] = x;  // 男性x与女性y订婚
}

// 寻找稳定婚姻
void ffind() {
    while (!q.empty()) {
        int x = q.front(); q.pop();  // 取出未订婚男性x
        int y = ml[x][nt[x]++];  // 男性x向第nt[x]偏好的女性y求婚
        
        // 若女性y未订婚，或x比y当前未婚夫更受偏好
        if (fh[y] == 0 || rk[y][x] < rk[y][fh[y]])
            engage(x, y);  // 女性y接受x的求婚
        else
            q.push(x);  // 求婚被拒绝，x下次继续求婚
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        init();
        ffind();
        
        // 按男性字典序输出配对结果
        for (int i = 1; i <= 30; i++) 
            if (fw[i])  // 只输出存在的男性（i<=n）
                printf("%c %c\n", 'a' + i - 1, 'A' + fw[i] - 1);
        
        if (T) printf("\n");  // 测试用例间输出空行
    }
    return 0;
}

关键步骤说明

1. 数据编码：

   • 男性用小写字母表示，编码为1~n（'a'-'a'+1=1，'b'-'a'+1=2...）
   • 女性用大写字母表示，编码为1~n（'A'-'A'+1=1，'B'-'A'+1=2...）

2. 偏好存储：

   • ml[x][j]：男性x的第j个偏好女性编号
   • rk[y][x]：女性y对男性x的偏好排名，数值越小越喜欢

3. 求婚机制：

   • 未订婚男性按偏好顺序求婚（nt[x]记录当前求婚进度）
   • 女性比较求婚者与当前未婚夫的偏好排名，选择更优者

4. 稳定婚姻证明：

   • 算法终止时，所有男性和女性都订婚
   • 不存在(m,f)使得f更喜欢m且m更喜欢f，满足稳定婚姻定义
   • 男性按偏好顺序求婚，确保结果为男性最优

算法复杂度分析

• 时间复杂度：O(n²)

  • 每个男性最多向n个女性求婚，总求婚次数O(n²)
  • 每次求婚判断女性偏好为O(1)操作

• 空间复杂度：O(n²)

  • 存储男女偏好列表需要O(n²)空间
  • 队列和临时变量为O(n)空间

示例解析

以第一个测试用例为例：

• 男性偏好：
  • a: BAC → 偏好顺序B(2), A(1), C(3)
  • b: BAC → 偏好顺序B(2), A(1), C(3)
  • c: ACB → 偏好顺序A(1), C(3), B(2)
• 女性偏好：
  • A: acb → 偏好顺序a(1), c(3), b(2)
  • B: bac → 偏好顺序b(2), a(1), c(3)
  • C: cab → 偏好顺序c(3), a(1), b(2)

求婚过程：

1. 初始队列：a, b, c
2. a向B求婚，B未订婚，a与B订婚
3. b向B求婚，B比较a和b：B对a的排名是2，对b的排名是1 → 选择b，a恢复单身入队
4. a向A求婚，A未订婚，a与A订婚
5. c向A求婚，A比较a和c：A对a的排名是1，对c的排名是3 → 拒绝c，c入队
6. c向C求婚，C未订婚，c与C订婚
7. 最终配对：a-A, b-B, c-C，符合男性最优稳定婚姻。