CF1783F Double Sort II

越飞翮
2023-12-01

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

题目Link

题目大意

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

  • 选择一个 i i i ,在 A , B A,B A,B 中分别找到 a x = b y = i a_x=b_y=i ax=by=i
  • s w a p   ( a x , a i ) swap\ (a_x,a_i) swap (ax,ai) ( b y , b i ) (b_y,b_i) (by,bi)

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

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

那么对于两个序列,环与环之间产生了交点,使得原来在 A A A 被动归位的点在 B B B 序列中可能不能被动归位,也就不能使得操作次数减少,所以要使操作次数减少,应使 A , B 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;
}

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

 类似资料:

相关阅读

相关文章

相关问答