「BZOJ1119」[POI2009] SLO
Description
对于一个1-N的排列(ai)，每次你可以交换两个数ax与ay(x<>y)，代价为W(ax)+W(ay) 若干次交换的代价为每次交换的代价之和。请问将(ai)变为(bi)所需的最小代价是多少。
Input
第一行N。第二行N个数表示wi。第三行N个数表示ai。第四行N个数表示bi。 2<=n<=1000000 100<=wi<=6500 1<=ai,bi<=n ai各不相等，bi各不相等 (ai)<>(bi) 样例中依次交换数字(2,5)(3,4)(1,5)
Output
一个数，最小代价。
Sample Input
6
2400 2000 1200 2400 1600 4000
1 4 5 3 6 2
5 3 2 4 6 1
2400 2000 1200 2400 1600 4000
1 4 5 3 6 2
5 3 2 4 6 1
Sample Output
11200
HINT
感谢MT大牛贡献译文.
题解
同牛排序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans,sum[1000005]; int n,cnt,ovmn=inf; int mn[1000005],size[1000005]; int a[1000005],pos[1000005],to[1000005],w[1000005]; bool vis[1000005]; void solve() { for(int i=1;i<=n;i++)ovmn=min(ovmn,w[i]); for(int i=1;i<=n;i++) if(!vis[i]) { cnt++; mn[cnt]=w[a[i]]; int k=i; while(1) { vis[k]=1; mn[cnt]=min(mn[cnt],w[a[k]]); sum[cnt]+=w[a[k]]; size[cnt]++; k=to[k]; if(k==i)break; } } for(int i=1;i<=cnt;i++) { ll t1=(ll)(size[i]-2)*mn[i]+sum[i]; ll t2=(ll)(size[i]+1)*ovmn+sum[i]+mn[i]; ans+=min(t1,t2); } } int main() { n=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) { int x=read(); pos[x]=i; } for(int i=1;i<=n;i++) to[i]=pos[a[i]]; solve(); printf("%lld",ans); return 0; } |
Subscribe
计数器 9855313
OI 课件=>
OI 课件=>