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 longusing 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;
}