题解：AT_abc233_f [ABC233F] Swap and Sort

思路：

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

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

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

代码：

CPP

#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;
}

题解：AT_abc233_f [ABC233F] Swap and Sort

文章操作

思路：

代码：

相关推荐

评论

题解：AT_abc233_f [ABC233F] Swap and Sort