poj 3270 Cow Sorting 夜

http://poj.org/problem?id=3270

给n头牛 让你把他们升序排序 每次交换两个牛 交换花费是两个牛值之和

求最小花费

黑书上有 P248     求循环

每个循环进行判断  一个循环的花费有两种情况可能为最优

1 用循环内最小的花费牛 和其他牛 进行交换

2 或是用全局最小花费牛 先和本环内最小花费牛交换 然后一样  最后再交换回来就可以了

代码及其注释：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
#define LL long long

using namespace std;

const int N=10005;
struct node
{
    int I;
    int k;
}mem[N];
int MIN;
bool cmp(node x,node y)
{
    return x.k<y.k;
}
int polya(int n)
{
    bool had[N];
    memset(had,false,sizeof(had));
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        if(!had[i])//每个环 判断
        {
            had[i]=true;
            int num=1;
            int sum=mem[i].k;
            int m=mem[i].k;
            int l=mem[i].I;
            while(l!=i)
            {
                had[l]=true;
                num++;
                sum+=mem[l].k;
                m=min(m,mem[l].k);
                l=mem[l].I;
            }
            ans=ans+min((sum-m+m*(num-1)),((sum-m+MIN)-MIN+MIN*(num-1)+2*(MIN+m)));//两种情况取最小
            //cout<<ans<<endl;
        }
    }
    return ans;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        MIN=N;
        for(int i=1;i<=n;++i)
        {
            mem[i].I=i;;//位置
            scanf("%d",&mem[i].k);//花费
            MIN=min(MIN,mem[i].k);//求全局最小花费
        }
        sort(mem+1,mem+n+1,cmp);//排序
        printf("%d\n",polya(n));
    }
    return 0;
}