POJ 3270 Cow Sorting(置换循环节)

题目：有一串数字，要将它排列成升序，每次可以交换两个数，交换一次的代价为两数之和。要求代价最小。
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