P9070 [CTS2023] 琪露诺的符卡交换

· · 题解

[CTS2023] 琪露诺的符卡交换

本题题解参考了周子衡学长的题解

题意

一共有 n 种卡牌，每种卡牌有 n 张。有 n 个人，每人拿了 n^2 张卡牌中的 n 张，问如何交换他们手中的牌（每张牌只能被交换一次），才能使他们每人都拿到 n 种卡牌？

题解

我们先将拿牌情况排列成表格，第 i 行表示第 i 个人的拿牌情况。显然第 i 行里面的数可以随意交换。

学长给出了一个核心操作：对于每一对 i,j(1\le i\le j\le n)，交换 (i,j) 和 (j,i)。

这样最后每个人拿到的牌实际上对应着每一列的牌。

问题转化成如何安排每一行的牌的顺序，使得每一列都有 n 种牌。

我们做 n 次二分图匹配（种类匹配行数），根据 Hall 定理，这样匹配一定是有解的。

匹配完后输出方案即可。细节看代码。

代码

懒得打 dinic 了直接复制板子

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=410,M=100010;
const long long INF=1145141919810114514;
int n,m,s,t,a[N][N],b[N][N],c[N][N];
int fst[N],to[M],nxt[M],ecnt=1;
int dep[N],vis[N],cur[N];
ll val[M];
void adde(int u,int v,ll w){
    ecnt++;
    to[ecnt]=v;
    val[ecnt]=w;
    nxt[ecnt]=fst[u];
    fst[u]=ecnt;
}
void Adde(int u,int v){
    adde(u,v,1);
    adde(v,u,0);
}
queue<int>q;
bool bfs(){
    memset(dep,0,sizeof(dep));
    for(int i=1;i<=t;i++)cur[i]=fst[i];
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=fst[u];i;i=nxt[i]){
            int v=to[i];
            ll w=val[i];
            if(!dep[v]&&w){
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t];
}
ll dfs(int u,ll in){
    ll out=0;
    if(u==t)return in;
    for(int i=cur[u];i&&in;cur[u]=i=nxt[i]){
        int v=to[i];ll w=val[i];
        if(w&&dep[v]==dep[u]+1){
            ll ret=dfs(v,min(w,in));
            if(!ret)continue;
            val[i]-=ret;val[i^1]+=ret;
            in-=ret;out+=ret;
        }
    }
    return out;
}
void solve(){
    cin>>n;s=n*2+1,t=s+1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int k=1;k<=n;k++){
        memset(fst,0,sizeof(fst));
        memset(b,0,sizeof(b));
        ecnt=1;
        for(int i=1;i<=n;i++)Adde(s,i),Adde(i+n,t);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[i][j])Adde(i,n+a[i][j]),b[i][j]=ecnt;
            }
        }
        int ans=0;
        while(bfs())ans+=dfs(s,INF);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(a[i][j]&&val[b[i][j]]){
                    a[i][j]=0;
                    c[i][k]=j;
                }
            }
        }
    }
    cout<<n*(n-1)/2<<"\n";
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cout<<i<<" "<<c[i][j]<<" "<<j<<" "<<c[j][i]<<"\n";
        }
    }
}
int main(){
    int T;cin>>T;
    while(T--)solve();
}