[Usaco2007 Feb] bzoj1697 Cow Sorting牛排序 [置换群]

Description:
n个人，每个人权值不同。每次可以交换两个人，价值为他们的权值和。问排成升序的最小代价。

Solution:
分解成若干循环节，一个循环节的最小代价是最小值交换循环节大小-1次，其他交换一次。或者把全局最小值和当前最小值交换一下。

#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
struct data {
    int w, id;
    friend bool operator < (const data &a, const data &b) {
        return a.w < b.w;
    }
} a[N];
int n, ans;
int p[N], vis[N];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i].w);
        a[i].id = i;
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) {
        p[a[i].id] = i;
    }
    for(int i = 1; i <= n; ++i) {
        if(!vis[i] && p[i] != i) {
            int p = i, cnt = 0, mn = 0x3f3f3f3f, sum = 0;
            while(!vis[p]) {
                vis[p] = 1;
                ++cnt;
                sum += a[p].w;
                mn = min(mn, a[p].w);
                p = a[p].id;
            }
            sum -= mn;
            ans += min(sum + mn * (cnt - 1), sum + mn * 2 + a[1].w * (cnt + 1));
        }
    }
    printf("%d\n", ans);
    return 0;
}