1119: [POI2009]SLO
Time Limit: 30 Sec Memory Limit: 162 MB Submit: 560 Solved: 271 [ ][ ][ ]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大牛贡献译文.
Source
【题解】【与POJ 2370很像,只是价值为w[i]】
#include#include #include #define ll long longusing namespace std;int a[1000010],cnt[1000010],n;bool p[1000010];ll v[1000010],minn=0x7fffffff,ans;int main(){ int i,j; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%lld",&v[i]),minn=min(minn,v[i]); for(i=1;i<=n;++i) scanf("%d",&a[i]); for(i=1;i<=n;++i) {int x; scanf("%d",&x),cnt[x]=i; } for(i=1;i<=n;++i) if(!p[i]) { ll t=0,sum=0,mn=0x7fffffff; j=i; while(!p[j]) { t++; sum+=v[a[j]]; mn=min(mn,v[a[j]]); p[j]=1; j=cnt[a[j]]; } if (t>=2) { ll t1=sum+(t-2)*mn; ll t2=sum+mn+(t+1)*minn; ans+=min(t1,t2); } } printf("%lld\n",ans); return 0; }