1119: [POI2009]SLO

也不算什么难题。。求出所有的置换，再在每个置换中讨论，ans=min(用置换中最小值换所有元素的代价；有全局最小值换置换中最小元素，用全局最小元素换所有元素，再将最小元素换回来),详见代码。。

#include<cstdio>
#include<cstring>
typedef long long ll;
bool can[1000001];
ll minc=~0u>>1,s=0,mins,sum,ans=0;
int cost[1000001],g[1000001];
int n,a[1000001],b[1000001],w[1000001],fb[1000001];
ll min(ll a,ll b){return a<b? a:b;}
void done(int i){
    //printf("%d\n",i);
    s=0;
    g[++s]=i;
    mins=~0u>>1;
    can[i]=false;
    mins=min(mins,cost[i]);
    sum=cost[i];
    int j=a[i];
    while (j!=i){
        g[++s]=j;
        can[j]=false;
        mins=min(mins,cost[j]);
        sum+=cost[j];
        j=a[j];
    }
    //printf("%d %d %d %d\n",s,sum,mins,minc);
    ans+=min(sum+(s-2)*mins,sum+minc*(s+1)+mins);
}
int main(){
    scanf("%d",&n);
    memset(can,true,sizeof(can));
    for (int i=1;i<=n;i++) scanf("%d",&w[i]);
    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++) fb[b[i]]=i;
    for (int i=1;i<=n;i++) a[i]=fb[a[i]];
    for (int i=1;i<=n;i++){
        cost[fb[i]]=w[i];
        minc=min(minc,w[i]);
    }
    //for (int i=1;i<=n;i++) printf("a[%d]=%d cost[%d]=%d\n",i,a[i],i,cost[i]);
    for (int i=1;i<=n;i++){
        if (can[i]) done(i);
    }
    printf("%lld\n",ans);
}