poj3270 Cow Sorting-------置换群
#include<iostream>#include<cstdlib>#include<stdio.h>#include<algorithm>using namespace std;int a[10010];int c[10010];struct Node{ int id; int num;}node[10010];int cmp(Node a,Node b){ return a.num<b.num;}int main(){ int n; while(scanf("%d",&n)!=EOF) { int minn=100000; int sum1=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum1+=a[i]; node[i].num=a[i];node[i].id=i; if(a[i]<minn) minn=a[i]; c[i]=i; } sort(node+1,node+n+1,cmp); for(int i=1;i<=n;i++) { int t; if(a[i]!=0) { int count=1; t=a[i]; int d=node[c[i]].id; if(a[d]<t) t=a[d]; while(d!=i) { count++; d=node[d].id; if(a[d]<t) t=a[d]; } int v=(count-2)*t;int w=(count+1)*minn+t; sum1+=v<w?v:w; a[i]=0; } } cout<<sum1<<endl; }}