題目：有一串數字，要將它排列成升序，每次可以交換兩個數，交換一次的代價為兩數之和。要求代價最小。
http://poj.org/problem?id=3270
經典的置換題目，黑書中有詳細介紹。
將原有數列排序之後，得到目標串，這樣就與原串形成了置換。
這樣的置換中分為多個循環，最優解當然是在循環內部進行交換，而循環間的交換只會增加代價。而在一個循環內部的最優解又是用循環中最小的數，依次與其它數進行交換，如果循環節長度為m,那麼最小的數需要交換m-1次，而其它數各一次。
但是這樣並不一定最優，因為有一種特殊情況，就是用循環外的一個數，與循環內的所有數交換，利用這個非常小的數進行中介。
那麼最終就是有兩種情況。一種是用循環內部最小的數為中介，另外一種就是用整個的最小的數為中介交換。
找到每個循環節的長度以及最小元素。
[cpp]
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100005
#define inf 1<<29
#define MOD 2007
#define LL long long
using namespace std;
struct Node{
int val;//循環中的最小值
int cnt;//循環節長度
}a[N];
int n,m[N],tot,t[N];
bool flag[N];
void dfs(int u){
for(int i=0;i<n;i++){
if(t[i]==u&&!flag[i]){
flag[i]=true;
a[tot].cnt++;
a[tot].val=min(a[tot].val,t[i]);
dfs(m[i]);
}
}
}
int main(){
while(scanf("%d",&n)!=EOF){
int sum=0,mmin=1<<30;
for(int i=0;i<n;i++){
scanf("%d",&m[i]);
sum+=m[i];
t[i]=m[i];
mmin=min(mmin,m[i]);
}
sort(m,m+n);
tot=0;
for(int i=0;i<n;i++){
if(flag[i]) continue;
a[tot].val=t[i];
a[tot].cnt=1;
flag[i]=true;
dfs(m[i]);
tot++;
}
for(int i=0;i<tot;i++)
sum+=min(a[i].val*(a[i].cnt-2),mmin*(a[i].cnt+1)+a[i].val);
printf("%d\n",sum);
}
return 0;
}
作者：ACM_cxlove
