CF1783F Double Sort II

好题。
通解思路：遇到交换题尝试考虑环。

题目Link

题目大意

给定两个由 $[1,n]$ 组成的长度为 $n$ 的序列 $A,B$，每次进行如下操作：

• 选择一个 $i$ ，在 $A,B$ 中分别找到 $a_x=b_y=i$
• $swap(a_x,a_i)$ 和 $(b_y,b_i)$

求最小的操作次数并输出操作过程。

一般来说，都会先去考虑单独一个序列的情况。
将序列的交换关系转成边，序列会由多个环组成，每个环都会使得一个点被动归位，那么答案为 $n-$ 环 的个数。

那么对于两个序列，环与环之间产生了交点，使得原来在 $A$ 被动归位的点在 $B$ 序列中可能不能被动归位，也就不能使得操作次数减少，所以要使操作次数减少，应使 $A,B$ 中被动归位点位置相同，用匈牙利算法解决即可。

Code

#include<bits/stdc++.h>
using namespace std;
int n,ta,tb,ans,a[3005],b[3005],ca[3005],cb[3005],bz[3005],t[3005];
struct qh{int v,nt;};
vector<qh> E[3005];
bool dfs(int x){
    for(int i=0;i<E[x].size();i++){
        int v=E[x][i].nt;
        if(!bz[v]&&(bz[v]=1)&&(!t[v]||dfs(t[v]))&&(t[v]=x)) return 1;
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    for(int i=1;i<=n;i++) scanf("%d",b+i);
    for(int i=1;i<=n;i++){
        if(!ca[i]){
            ca[i]=++ta;
            int nw=i;
            while (a[nw]!=i) ca[a[nw]]=ta,nw=a[nw];
        }
        if(!cb[i]){
            cb[i]=++tb;
            int nw=i;
            while (b[nw]!=i) cb[b[nw]]=tb,nw=b[nw];
        }
    }
    // for(int i=1;i<=n;i++) printf("%d ",ca[i]);puts("");
    // for(int i=1;i<=n;i++) printf("%d ",cb[i]);puts("");
    for(int i=1;i<=n;i++) E[ca[i]].push_back((qh){i,cb[i]});
    for(int i=1;i<=ta;i++){
        memset(bz,0,sizeof(bz));
        ans+=dfs(i);
    }
    printf("%d\n",n-ans);
    for(int i=1;i<=ta;i++) for(int j=0;j<E[i].size();j++) if(t[E[i][j].nt]!=i) printf("%d ",E[i][j].v);else t[E[i][j].nt]=0;
    return 0;
}

---

有时候序列元素交换问题并不容易理解交换的过程，要善于转化。