Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 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 1

Sample Output

11200

题解

置换群
什么叫置换呢
置换就是给你两个全排列(ai)(bi)
然后一一对应互换 比如说规则中说1->5 那么这样的话1永远只能变成5
然后问你一个全排列最小花费多少到第二个全排列
这个东西由于一一对应 我们一定可以连边出环
比如说针对这个样例而言 我们有这么几个环
(6)(3,4)(1,2,5)

一个向下连边的过程
然后针对一个环
我们有两种方法
第一种方法就是说我们让环内花费最少的元素转一圈 把所有的都交换回去
这样的话总的花费ans1=sum+(len-2)*min
这里面的sum代表整个环的权值 min代表环内的最小值 len代表环的长度

第二种方法就是我们引入环外的一个小元素
这样的话总的花费ans2=sum+min+(len+1)*minn
这里面的minn代表所有数中最小的 其余的同上面

然后这就是答案了

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏