BZOJ1119 - Click Here
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
一个数，最小代价。
Solutions
和BZOJ1697一样呢。
既然给出了置换，那大概就是要对每个循环讨论一下吧。
因此先对置换进行分解，然后考虑每个循环。
对于一个循环，有两种处理方法：
用循环内的最小值跑一圈。此时代价为$sum+min(len-2)$
或者选择循环外的一个最小值，让它与循环内的最小值交换，然后跑一圈。此时代价为$sum+min+MIN(len+1)$
其中$min$表示循环内最小值，$MIN$表示循环外最小值。
CODE
CODE - Click Here