P9070 [CTS2023] 琪露诺的符卡交换 题解
LRC0511
·
·
题解
一些记号和约定
$\forall a,b\in S_n,a\circ b$ 表示置换的复合。
$\forall a \in S_n$，$a^{-1}$ 表示置换 $a$ 的逆，即唯一满足 $a\circ a^{-1}=a^{-1} \circ a =e$ 的元素，其中 $e\in S_n$ 是单位元，满足 $\forall a\in S_n,a\circ e = e\circ a=a$。
$\forall a\in S_n,x \in \{1,2,\cdots,n\}$，记 $a(x)$ 表示原来第 $x$ 个位置在置换 $a$ 作用后抵达的位置。
循环 $(a_0,\cdots,a_{k-1})$ 表示置换 $p$，满足 $p(a_i)=a_{(i+1) \bmod k}$，保持其它元素不变。特别地，当 $k=2$ 时被称作对换，即交换 $a_0,a_1$。
## 题意简述
给定一个 $n\times n$ 的方阵，其中 $1\sim n$ 中的整数皆恰好出现 $n$ 次，求置换 $p \in S_{n^2}$ 满足：
1. 经过 $p$ 作用后，方阵中的每一行都是 $1\sim n$ 的排列。
2. $p$ 是若干个不相交对换的合成。
多组数据，$\sum n \leq 200$。
## 解法
子任务 $1$ 可以直接将矩阵转置得到，而转置恰好是满足上述条件 $2$ 的一个置换（不妨记作 $t$），这启发我们考察 $t$ 的共轭类：
$\{p\circ t \circ p^{-1}: \forall p \in S_{n^2}\}$。
我们将 $t$ 分解为若干不相交对换：
$$t=(a_1,b_1)\circ \cdots\circ(a_k,b_k)$$
不难验证，有：
$$p\circ t \circ p^{-1} = (p(a_1),p(b_1))\circ \cdots\circ(p(a_k),p(b_k))$$
因此它也是若干对换的合成，我们只需寻找一个合法的 $p$，使得 $p^{-1}\circ t \circ p$ 作用后每行都是排列就够了。
任意选取 $p$ 不可取，但如果我们将 $p$ 限定为每行内部的置换的合成，行与行之间互不干扰，那么最后的 $p^{-1}$ 就失去了意义，只需要在 $t\circ p$ 作用后每行都是排列即可，而这等价于在 $p$ 作用后，每列都是排列。
于是问题转化为：将每行内部重新排列后，使得每列都是排列。
我们建立一张二分图，左部点表示每行，右部点表示 $1\sim n$ 中的数，每行向其所有 $n$ 个元素连边（允许重边）。
我们只需将边集划分为 $n$ 组互不相交的匹配，每组匹配就是对应的列中填的元素。
注意到每个点的度数都是 $n$，则该二分图的最小边染色数为 $n$，且在任意的最小边染色方案中，每种颜色的边均构成一组匹配。
因此此题必然有解，我们只需利用 [CF600F](https://www.luogu.com.cn/problem/CF600F) 的做法，即可在 $O(n^3)$ 的时间复杂度内求出 $p$。
最后输出方案时，只需输出 $p^{-1}\circ t\circ p$ 即可。
## 代码实现
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=405;
namespace Paint
{
int to[N][N],pos[N][N];
inline void init(int n)
{
for(int i=1;i<=2*n;i++)
for(int j=1;j<=2*n;j++)
to[i][j]=pos[i][j]=0;
}
void dfs(int u,int v,int id,int c,int nc)
{
to[u][c]=id,pos[u][c]=v;
int nxid=to[v][c],nxp=pos[v][c];
to[v][c]=id,pos[v][c]=u;
if(!nxid) return;
to[nxp][c]=pos[nxp][c]=0;
dfs(v,nxp,nxid,nc,c);
}
inline void add(int u,int v,int id)
{
int x=1,y=1;while(to[u][x]) x++; while(to[v][y]) y++;
if(x==y) {to[u][x]=to[v][y]=id,pos[u][x]=v,pos[v][y]=u;return;}
dfs(u,v,id,x,y);
}
}
int n,a[N][N],rp[N][N];
inline void work()
{
cin>>n;Paint::init(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j],Paint::add(i,a[i][j]+n,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
rp[i][j]=Paint::to[i][j];
cout<<n*(n-1)/2<<"\n";
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
cout<<i<<" "<<rp[i][j]<<" "<<j<<" "<<rp[j][i]<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;cin>>T;while(T--) work();
return 0;
}
```