题解：AT_abc233_f [ABC233F] Swap and Sort

YFF1 · 2024-12-10 13:35:56 · 题解

思路：

首先，这是一道构造题。题目中说到，要求构造一种能够通过不超过限度次数的交换使得序列变得有序。由于题目中没有说必须要最优，所以只需要构造一种不超过限度的即可。

有一种较为优秀的构造方法：首先把各种交换关系抽象成一张图，如果有一个点和它想要变成的值不在同一个连通块里面，就说明无论怎样换都换不出有序序列。此时直接输出无解。然后，在图上每个连通块内部选取一些边，构造一棵生成树。从树上的叶子节点开始，每个点把它想要的权值通过和相邻节点交换权值换给它。处理完毕叶子节点，把处理完的节点“删掉”。然后按照同样的方式处理新的叶子节点。最后就可以把每个节点都换成它的对应值了。

为什么要换叶子节点呢？因为这种构造方式的核心就是每个处理完毕的节点都不会受到影响。这样每个点最多只会和剩下的所有点都交换一次，很大程度上避免了操作的重复。尝试取到极限数据，这样的构造方式刚好可以通过样例。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,p[1005],a[200005],b[200005],fa[200005],edge[1005][1005];
vector<int>ans,g[200005];
bool vis[10005];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
bool spp(int x,int fa,int num){
    if(p[x]==num)return true;
    for(int i:g[x]){
        if(i==fa)continue;
        if(spp(i,x,num)){
            ans.push_back(edge[i][x]);
            swap(p[x],p[i]);
            return true;
        }
    }
    return false;
}
void dfs(int x){
    vis[x]=1;
    for(int i:g[x]){
        if(!vis[i])dfs(i);
    }
    if(!spp(x,0,x)){
        cout<<-1;
        exit(0);
    }
}
signed main () {
    cin>>n;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
    cin>>m;
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&a[i],&b[i]);
        edge[a[i]][b[i]]=i;
        edge[b[i]][a[i]]=i;
        if(find(a[i])!=find(b[i])){
            fa[find(a[i])]=fa[find(b[i])];
            g[a[i]].push_back(b[i]);
            g[b[i]].push_back(a[i]);
        }
    }
    for(int i=1;i<=n;i++){
        if(find(p[i])!=find(i)){
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(!vis[i])dfs(i);
    }
    cout<<ans.size()<<endl;
    for(int i:ans)cout<<i<<" ";
    return 0;
}