[CTS2023] 琪露诺的符卡交换

· · 题解

现在的小伙子出的题还是相当的规范，没有被抹杀掉创造力！

先考虑第二档部分分囊给俎，嗯交换比较困难，我们考虑给他车一转，这样我们惊奇的发现它满足了每行都有 n 种钥匙！这给我们启发从转置的角度入手这个题。

那么实际上转置之后就是一个做板凳的问题了哈。每个人手里钥匙的顺序实际上是不影响的。我们考虑把每种钥匙挂在一个板凳上，第 i 行有一个第 j 种钥匙就从左 i 往右 j 连一条边。第 i 个人手里该增么换捏？每次给每种钥匙匹配一个板凳，然后把匹配的边删掉。这样根据墙（\text{Hall}）定理每次都有完美匹配！

对着代码理解一下咩！我的代码写得还是很清楚的哈。

#include <bits/stdc++.h>
using namespace std;
bool used[210];
int head[210],go[66666],last[66666],fl[66666],cnt,T,n,ans[210][210],seat[210],hp[210][210],ct,lp[66666],zh[66666];
void add(int a,int b)
{
  go[++cnt]=b;
  last[cnt]=head[a];
  head[a]=cnt;
}
bool sit(int a)
 {
  if(used[a])return 0;
   used[a]=1;
  for(int i=head[a];i;i=last[i])
   {if(!fl[i])
   if(!seat[go[i]] ||sit(seat[go[i]])){seat[go[i]]=a;return 1;
  }
 }
  return 0;
}
int main()
 {
  scanf("%d",&T);
 while(T--){
   scanf("%d",&n);
  for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
    {
     int x;
    scanf("%d",&x);
    add(i,x);
    zh[++ct]=j;
    lp[ct]=hp[i][x];
    hp[i][x]=ct;
   }
 for(int i=1;i<=n;i++){
  memset(seat,0,sizeof seat);
   for(int j=1;j<=n;j++)
   {memset(used,0,sizeof(used));
    sit(j) ;
   }
  for(int j=1;j<=n;j++)
  {
   int x=seat[j];
   ans[x][i]=zh[hp[x][j]] ;
   hp[x][j] =lp[hp[x][j]];
   for(int k=head[x];k;k=last[k])
    {if(!fl[k]&&go[k]==j)
     {
      fl[k]=1;
       break;
     }
   }
  }
 }
 printf("%d\n",n*(n-1)/2);
 for(int i=1;i<=n;i++)
  {for(int j=1;j<i;j++){
    printf("%d %d %d %d\n",i,ans[i][j],j,ans[j][i]);}
 }
  memset (head,0,sizeof head);
  memset(go,0,sizeof go);
  cnt=0 ;
  memset(last,0,sizeof (last));
 memset(ans,0,sizeof ans) ;
  memset(fl,0, sizeof fl);ct=0;
  memset (hp, 0 ,sizeof( hp )) ;
  memset(lp ,0 ,sizeof (lp));
  memset(zh,0,sizeof( zh));}
   return 0;
  }