poj 3270 Cow Sorting (置換群)

/*
對于每一個群，我們有兩種換發：
1.群裡換，拿群裡最小的數t與其他每個數交換，共k-1次,花費為：sum+(k-2)*t.
2.将這個數列最小的數minn，拉入這個群，與該群最小的數t交換，然後用這個最小的數與其他數交換k-1次，然後再将minn與t換回來，這樣
花費為：sum+t+(k+1)*minn
那麼最小花費我們取兩者中最小的，即sum+min{(k-2)*t,t+(k+1)*minn}.
*/
# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <iostream>
using namespace std;
struct node
{
    int id;
    int num;
};
struct node a[10010];
bool cmp(node a1,node a2)
{
    return a1.num<a2.num;
}
int main()
{
    int sum1,i,minn,n;
    int b[10010],c[10010];
    while(~scanf("%d",&n))
    {
        sum1=0;
        minn=100010;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            a[i].num=b[i];
            a[i].id=i;
            sum1+=b[i];
            if(b[i]<minn)
                minn=b[i];
            c[i]=i;
        }
        sort(a+1,a+n+1,cmp);
        for(i=1;i<=n;i++)
        {
            int t;
            if(b[i]!=0)
            {
                int count=1;
                t=b[i];
                int d=a[c[i]].id;
                if(b[d]<t)
                    t=b[d];
                while(d!=i)
                {
                    count++;
                    d=a[d].id;
                    if(b[d]<t)
                        t=b[d];
                }
                int v=(count-2)*t;
                int w=(count+1)*minn+t;
                sum1+=min(v,w);
                b[i]=0;
            }
        }
        printf("%d\n",sum1);
    }
    return 0;
}