1119: [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 1Sample Output
11200
HINT
感谢MT大牛贡献译文.
【分析】
跟BZOJ 1119一模一样,记得用LL。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1000010
#define INF 0xfffffff
#define LL long long LL w[Maxn]; struct node
{
LL a,b;
}t[Maxn]; bool cmp(node x,node y) {return x.a<y.a;}
LL mymin(LL x,LL y) {return x<y?x:y;} bool vis[Maxn]; int main()
{
LL n,mnn=INF;
scanf("%lld",&n);
for(LL i=;i<=n;i++) {scanf("%lld",&w[i]);mnn=mymin(mnn,w[i]);}
for(LL i=;i<=n;i++) scanf("%lld",&t[i].a);
for(LL i=;i<=n;i++) scanf("%lld",&t[i].b);
sort(t+,t++n,cmp);
memset(vis,,sizeof(vis));
LL ans=;
for(LL i=;i<=n;i++) if(vis[i]==)
{
LL x=i,mn=INF,h=;
LL cnt=;
while(vis[x]==)
{
mn=mymin(mn,w[x]);
vis[x]=;
cnt++;
h+=w[x];
x=t[x].b;
}
ans+=mymin(h+(cnt-)*(LL)mn,h+mn+(cnt+)*(LL)mnn);
}
printf("%lld\n",ans);
return ;
}
2017-01-12 20:13:51