whu1018-king kong(置换群，找循环节).cpp

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

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int n, min_cost;
int ss[5100], ts[5100];
int pos1[1<<16];
bool vis[5100];

int main()
{
	int i,minp;
	while(scanf("%d", &n), n) {
		min_cost = 0;
		minp = INT_MAX;
		memset(vis,0,sizeof(vis));
		for(i=1;i<=n;i++) {
			scanf("%d", ss+i);
			minp = min(minp, ss[i]);
			min_cost += ss[i];
			pos1[ ss[i] ] = i;
		}
		for(i=1;i<=n;i++) {
			scanf("%d", ts+i);
		}
		//find circle
		for(i=1;i<=n;i++) {
			if(!vis[i]) {
				int tpos = i;
				int len = 0;
				int mmin = INT_MAX;
				do {//find mininum in circle
					vis[tpos] = true;
					mmin = min(mmin, ts[tpos]);
					tpos = pos1[ ts[tpos] ];
					len ++;
				} while(tpos != i);
				//inner exchange < inner-outer exchange
				min_cost += min((len-2)*mmin , (len+1)*minp + mmin);
			}
		}
		printf("%d\n", min_cost);
	}
}