「CTS2023」琪露诺的符卡交换 题解

题目大意

有 $n$ 个人，每人有 $n$ 张卡片，共有 $n$ 种卡片类型。需要通过交换操作使得每个人恰好持有 $n$ 种不同的卡片，且每张卡片最多被交换一次。

解题思路

关键观察

1. 问题转化：这实际上是一个二分图多重匹配问题

   • 左部：$n$ 个人
   • 右部：$n$ 种卡片类型
   • 每个人需要与 $n$ 种不同的卡片匹配

2. 匹配分解：可以将问题分解为 $n$ 个完美匹配

   • 每个完美匹配表示一种"分配方案"
   • 第 $t$ 轮匹配决定第 $t$ 次交换的信息

算法核心

阶段一：建立初始图

• 对于每个人 $i$，向他拥有的所有卡片类型连边
• 记录每张卡片的具体位置 c[i][x] 存储卡片类型 $x$ 在人物 $i$ 手中的位置

阶段二：寻找 $n$ 个完美匹配

for (int t = 1; t <= n; t++) {
    // 使用匈牙利算法找完美匹配
    // 记录这个匹配：人物 i 在轮次 t 匹配到卡片类型 res[i]
    // 记录对应的卡片位置 pos[i][t]
}

阶段三：构造交换序列

• 对于任意两个人 $i < j$，在第 $i$ 轮和第 $j$ 轮中交换他们匹配到的卡片
• 总共需要 $\frac{n(n-1)}{2}$ 次交换

代码解析

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

const int mm = 220;
int n, vis[mm], res[mm], pos[mm][mm];
vector<int> e[mm];          // e[i]: 人物i拥有的卡片类型
vector<int> c[mm][mm];      // c[i][x]: 人物i拥有的类型x卡片的位置

// 匈牙利算法找增广路
bool match(int u) {
    for (int i = 0; i < e[u].size(); i++) {
        int v = e[u][i];  // 卡片类型v
        
        if (vis[v]) continue;
        vis[v] = true;
        
        // 如果v未被匹配，或者已匹配点可以找到新的匹配
        if (!res[v] || match(res[v])) {
            res[v] = u;   // 记录匹配
            return true;
        }
    }
    return false;
}

void Solve() {
    n = read();
    
    // 读入数据并建图
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            int x = read();  // 卡片类型
            e[i].push_back(x);
            c[i][x].push_back(j);  // 记录位置
        }
    
    // 找n个完美匹配
    for (int t = 1; t <= n; t++) {
        memset(res, 0, sizeof(res));  // 清空匹配
        
        // 为每个人找匹配
        for (int i = 1; i <= n; i++) {
            memset(vis, 0, sizeof(vis));
            match(i);
        }
        
        // 记录这个匹配的结果
        for (int i = 1; i <= n; i++) {
            int x = res[i];  // 卡片类型i匹配到人物x
            pos[x][t] = c[x][i].back();  // 记录卡片位置
            c[x][i].pop_back();          // 移除已使用的卡片
            // 移除这条边，避免重复使用
            e[x].erase(find(e[x].begin(), e[x].end(), i));
        }
    }
    
    // 输出交换序列
    printf("%d\n", n * (n - 1) / 2);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            printf("%d %d %d %d\n", i, pos[i][j], j, pos[j][i]);
}

int main() {
    int T = read();
    while (T--) Solve();
    return 0;
}

算法正确性

为什么这样构造？

• 完美匹配存在性：根据 Hall 定理，由于每种卡片恰好有 $n$ 张，每个人需要 $n$ 种不同卡片，完美匹配一定存在
• 交换有效性：第 $i$ 个人和第 $j$ 个人交换他们在第 $i$ 轮和第 $j$ 轮匹配到的卡片，可以保证：
  • 每张卡片最多被交换一次
  • 最终每个人持有 $n$ 种不同的卡片

复杂度分析

• 时间复杂度：$O(T \cdot n^4)$
  • 每次匈牙利算法：$O(n^3)$
  • 运行 $n$ 次：$O(n^4)$
• 空间复杂度：$O(n^2)$

样例验证

样例1

输入：
3
1 2 2
2 3 3  
3 1 1

算法会找到3个完美匹配，然后构造交换序列，输出：

2
1 3 3 1
2 3 3 2

样例2

输入：
3
1 2 3
2 3 1
3 2 1

由于初始状态已满足条件，输出：

0

总结

本题的巧妙解法在于：

1. 匹配分解：将复杂问题分解为多个完美匹配
2. 匈牙利算法：高效求解二分图匹配
3. 构造性证明：通过具体的交换序列证明解的存在性

这种"匹配分解+构造交换"的思路对于解决类似的分配和交换问题具有很好的参考价值。