【解題報告】POJ 3270 Cow 置換群基礎 -- 輪換

寫這麼多，不知道有沒有了解錯。

/*
	POJ 3270 Cow 置換群基礎 -- 輪換
	題意：
	給一個序列 A[1 8 9 7 6] 僅允許一次交換兩個元素，交換代價為兩個數字之和
	求最小的代價和使得序列有序（遞增）
	元素不會重複
	方法：
	我們很容易算出 排序後的結果為A'[1 6 7 8 9] 也就是讓A序列通過交換變為A'序列，
	不過我們在這裡嘗試反過來考慮，将A'變為A
	A' [1 6 7 8 9]
	A  [1 8 9 7 6]
	對 A 每一列單獨分析，
	僅第一列：1不變 (暫且标記為1->1)
	僅第二列：要由6變為8 将 swap(A'(6),A'(8)) 标記為6->8
	僅第三列：要由7變為9 将 swap(A'(7),A'(9)) 标記為7->9
	僅第四列：要由8變為7 将 swap(A'(8),A'(7)) 标記為8->7
	僅第五列：要由9變為6 将 swap(A'(9),A'(6)) 标記為9->6
	我們突然發現最後的标記可以連接配接成一條 6->8->7->9  (這個[6 ,8 ,7 ,9]序列 called 循環||輪換||群)
	直接給出結論，如果我們要交換次數最少，那麼交換一定在一個輪換中進行（模拟下會發現如果不這樣，還有可能将有序的打亂去交換）
	對于這個題目，不妨貪心一下，在一個輪換中每次選取最小的元素進行交換，使得輪換有序。（Ⅰ）
	但這樣并不一定是最小代價
	因為存在上面的例子（[1 6 7 8 9]）
	我們還有可能每次選擇整個序列中的最小值去直接交換（Ⅱ）(因為最小值可能很小，而其他的都很大)。
	最後隻需要在ⅠⅡ之間取最大值即可
	題目至此得解
	符号解釋: swap(A'(6),A'(8)) A'序列中值為6的元素與A'序列中值為8的元素交換
*/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
#define CLR(a,v) memset(a,v,sizeof(a))
using namespace std;
typedef long long ll;
template<typename T>
T Min(T a,T b){
	return (a>b)?(b):(a);
}

const int N   = 1e4 + 10;
const int INF = (1<<30);

int a[N] , b[N] , id[N*10];
bool vis[N];

int n;
vector <int > store[N]; // 儲存循環節
void GetCircel(int x , int cnt){ // 求循環節 
	if(vis[x])return;
	store[cnt].push_back(a[x]);
	vis[x] = 1;
	GetCircel(id[b[x]] , cnt);
}

int main(){
	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	while(cin >> n){
		int mmin = INF;  // 全局最小值
		for(int i = 1 ; i <= n ; i++){
			scanf("%d", &a[i]);
			b[i]=a[i];
			mmin = Min(mmin,a[i]);
		}
		memset(vis , 0 , sizeof(vis));
		sort(a+1 , a+n+1);
		for(int i = 1 ; i <= n ; i++){
			id[a[i]] = i;
		}
		int cnt = 0 , ans = 0;
		for(int i = 1 ; i <= n ; i++){
			if(!vis[i])
				GetCircel(i , cnt++);
		}
		// 輸出循環節
		//for(int i = 0 ; i < n ; i++){
		//	if(!store[i].size())continue;
		//	for(int j = 0 ; j < store[i].size() ; j++){
		//		cout << store[i][j] <<" ";
		//	}cout << endl;
		//}
		for(int i = 0 ; i < cnt ; store[i++].clear() ){
			int size = store[i].size() , sum = 0;
			if(store[i].size()<=1)continue;
			int min = store[i][0];   // 循環節中最小值
			for(int j = 0 ; j < size ; j++){
				sum += store[i][j];
				min = Min(min , store[i][j]);
			}
			ans += sum + Min(min*(size-2) , mmin*(size+1) + min);
		}
		cout << ans << endl;
	}
	return 0;
}


/*
in
5
1 8 9 7 6
6
3 4 5 2 1 6

out
41 
16

*/