传送门：现在$POI$上的题洛谷都有了，还要$BZOJ$干什么
和$cow\ sorting$一样，只不过问$a_i \rightarrow b_i$
注意置换是位置而不是数值...也就是说要$i$的数值$a_i$要变到$b$中数值$a_i$的位置
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e6+5; typedef long long ll; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } int n,a[N],pos[N],w[N],f[N],Min=N; ll ans; bool vis[N]; int main(){ freopen("in","r",stdin); n=read(); for(int i=1;i<=n;i++) w[i]=read(),Min=min(Min,w[i]); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) pos[read()]=i; for(int i=1;i<=n;i++) f[i]=pos[a[i]]; for(int i=1;i<=n;i++) if(!vis[i]){ vis[i]=1; int u=f[i],len=1,mn=w[a[i]]; ll sum=w[a[i]]; while(u!=i) vis[u]=1,len++,mn=min(mn,w[a[u]]),sum+=w[a[u]],u=f[u]; ans+=sum+min((ll)mn*(len-2),mn+(ll)Min*(len+1)); } printf("%lld",ans); }
原文：http://www.cnblogs.com/candy99/p/6478915.html