首页 > 代码库 > 【BZOJ 1119】 1119: [POI2009]SLO (置换)
【BZOJ 1119】 1119: [POI2009]SLO (置换)
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
11200HINT
感谢MT大牛贡献译文.
【分析】
跟BZOJ 1119一模一样,记得用LL。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 1000010 8 #define INF 0xfffffff 9 #define LL long long 10 11 LL w[Maxn]; 12 13 struct node 14 { 15 LL a,b; 16 }t[Maxn]; 17 18 bool cmp(node x,node y) {return x.a<y.a;} 19 LL mymin(LL x,LL y) {return x<y?x:y;} 20 21 bool vis[Maxn]; 22 23 int main() 24 { 25 LL n,mnn=INF; 26 scanf("%lld",&n); 27 for(LL i=1;i<=n;i++) {scanf("%lld",&w[i]);mnn=mymin(mnn,w[i]);} 28 for(LL i=1;i<=n;i++) scanf("%lld",&t[i].a); 29 for(LL i=1;i<=n;i++) scanf("%lld",&t[i].b); 30 sort(t+1,t+1+n,cmp); 31 memset(vis,0,sizeof(vis)); 32 LL ans=0; 33 for(LL i=1;i<=n;i++) if(vis[i]==0) 34 { 35 LL x=i,mn=INF,h=0; 36 LL cnt=0; 37 while(vis[x]==0) 38 { 39 mn=mymin(mn,w[x]); 40 vis[x]=1; 41 cnt++; 42 h+=w[x]; 43 x=t[x].b; 44 } 45 ans+=mymin(h+(cnt-2)*(LL)mn,h+mn+(cnt+1)*(LL)mnn); 46 } 47 printf("%lld\n",ans); 48 return 0; 49 }
2017-01-12 20:13:51
【BZOJ 1119】 1119: [POI2009]SLO (置换)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。