题解：AT_abc233_f [ABC233F] Swap and Sort
kkxacj
·
·
题解
目前看上去应该没问题，如果有 hack 可以私信联系我。
思路
否则对于每一个数看 $id_i$ 与 $i$ 是否相等，不相等就跑一遍最短路，记录一下用了哪些边，具体的就是在求最短路是记录是由哪个点转过来的以及转过来用了那条边，然后以从 $id_i$ 到 $i$ 的顺序加入答案序列。
考虑枚举 $i$ 表示前 $i-1$ 的数都排好了，开始排第 $i$ 个，若 $i$ 到 $id_i$ 的最短路有前 $i-1$ 个的数，则需要在跑完后需要把这条路径其他点放回去，否则若路径上 $j = id_j$ 的个数比其他更多，也需要把这条路径其他点放回去，即按从 $id_i$ 到 $i$ 的顺序交换，但不换与 $i$ 相邻的点，会发现**只改变了 $i$ 和 $id_i$ 的值**，否则不放。
**code**
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace IO
{
template<typename T>
void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
template<typename T,typename... Args>
void read(T &_x,Args&...others){Read(_x);Read(others...);}
const int BUF=20000000;char buf[BUF],top,stk[32];int plen;
#define pc(x) buf[plen++]=x
#define flush(); fwrite(buf,1,plen,stdout),plen=0;
template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++top]=48+x%10;while(top) pc(stk[top--]);}
}
using namespace IO;
int n,m,a[10010],x,y,ok,ok1,xt[500010],yt[500010],v[10010],f[10010],id[200010],st[500010],cnt,bj[1010],bj1[1010],bj2[1010],cnt1,f1[10010];
vector<int>w[10010];
vector<int>w1[10010];
priority_queue<pair<int,int> > q;
inline int find(int x)
{
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
inline void bfs(int x)
{
while(!q.empty())
{
y = q.top().second;
q.pop();
v[y] = 0;
for(int i = 0;i < w[y].size();i++)
{
if(bj[w[y][i]] == 1e16 || bj[w[y][i]] > bj[y]+1)
{
bj[w[y][i]] = bj[y] + 1,bj1[w[y][i]] = y,bj2[w[y][i]] = w1[y][i];
if(!v[w[y][i]])
{
q.push(make_pair(-bj[w[y][i]],w[y][i]));
v[w[y][i]] = 1;
}
}
}
}
return;
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);
for(int i = 1;i <= n;i++) read(a[i]),f[i] = i,id[a[i]] = i;
read(m);
for(int i = 1;i <= m;i++) read(x),read(y),xt[i] = x,yt[i] = y,f[find(x)] = find(y),w[x].push_back(y),w[y].push_back(x),w1[x].push_back(i),w1[y].push_back(i);
for(int i = 1;i <= n;i++)
if(find(i) != find(id[i]))
{
print(-1);
flush();
return 0;
}//每次执行前保证前i-1个排好序
for(int i = 1;i <= n;i++)
if(i != id[i])
{
for(int j = 1;j <= n;j++) v[j] = bj1[j] = bj2[j] = 0,bj[j] = 1e16;
bj[id[i]] = 0,q.push(make_pair(0,id[i]));
bfs(id[i]);
cnt1 = 0,y = i; ok = ok1 = 0;
while(y != id[i])
{
if(id[y] == a[y] && id[y] < i) ok += n;//若有<i的点则一定要换回去
else if(id[y] == a[y]) ok++;
else ok1++;//记录
f1[++cnt1] = bj2[y];
y = bj1[y];
}
for(int j = cnt1;j >= 1;j--)
{
st[++cnt] = f1[j];
swap(id[a[xt[f1[j]]]],id[a[yt[f1[j]]]]);
swap(a[xt[f1[j]]],a[yt[f1[j]]]);
}
if(ok > ok1)//看是否将路径上其他点放回原位
{
for(int j = 2;j <= cnt1;j++)
{
st[++cnt] = f1[j];
swap(id[a[xt[f1[j]]]],id[a[yt[f1[j]]]]);
swap(a[xt[f1[j]]],a[yt[f1[j]]]);
}
}
}
print(cnt),pc('\n');
for(int i = 1;i <= cnt;i++) print(st[i]),pc(' ');
flush();
return 0;
```