cow sorting(置换群，最小花费置换).cpp

来自「杭电acm解题报告2001---2099.」· C++ 代码 · 共 55 行

//类似king kong
#include <cstdio>
#include <string>
#include <functional>
#include <algorithm>
using namespace std;

int g[10100],n;
bool vis[10100];
int pos[101000];

struct node {
	int v,p;
	bool operator < (const node & t) const {
		return v < t.v;
	}
}g2[10100];

int main()
{
	int i,j;
	int sum, mmin;
	while(scanf("%d", &n)==1) {
		sum = 0;
		mmin = INT_MAX;
		for(i=1;i<=n;i++) {
			scanf("%d", g+i);
			sum += g[i];
			g2[i].v = g[i];
			g2[i].p = i;
			mmin = min(mmin, g[i]);
			vis[i] = false;
		}
		sort(g2+1,g2+n+1);
		for(i=1;i<=n;i++) {
			pos[ g2[i].v ] = g2[i].p;
		}

		for(i=1;i<=n;i++) {
			if(!vis[i]) {
				int tpos = i;
				int len = 0;
				int tmin = INT_MAX;
				do {
					tmin = min(tmin, g[tpos]);
					vis[tpos] = true;
					tpos = pos[ g2[tpos].v ];
					len ++;
				} while(tpos != i);
				sum += min( (len-2)*tmin, (len+1)*mmin +tmin);
			}
		}
		printf("%d\n", sum);
	}
}