POJ 3270 Cow Sorting

問題

要素のスワップを繰り返して数列を昇順にソートしたい。数列中のXとYを入れ替える時のコストをX+Yとする。ソートに必要な最小コストを求めよ。

やりかた

数列を巡回置換のまとまりに分解する。
例えば(3,5,7,4,2,1,6)であれば(3,7,1,6)(5,2)(4)となる。

すると各まとまり（列）ごとに分けて計算すれば良くなる。各列のサイズをci、最小の要素をmi、和をsumiとし、全体の数列中の最小の要素をMiとすると答えは以下の数式で表せる。

以下ソース。

//置換群の列挙 O(nlogn)
template<typename T>
vector<vector<int> > perm_group(vector<T> src){
  vector<T> dst = src;
  sort(dst.begin(), dst.end());

  int N = src.size();
  map<T, int> src_index, dst_index;
  for(int i = 0; i < N; i++) 
    src_index[src[i]] = i, dst_index[dst[i]] = i;
  
  vector<bool> vis(N, false);
  vector<vector<int> > ret;
  for(int i = 0; i < N; i++){
    if(vis[i]) continue;
    int start = i, idx = i;
    vector<int> perm;
    perm.push_back(start);
    vis[start] = true;
    while(src_index[dst[idx]] != start){
      idx = src_index[dst[idx]];
      perm.push_back(idx);
      vis[idx] = true;
    }
    ret.push_back(perm);
  }
  return ret;
}

int main(int argc, char **argv){
  int N;
  scanf("%d", &N);
  vector<int> s(N);
  int min1 = INF;
  for(int i = 0; i < N; i++){
    scanf("%d", &s[i]);
    min1 = min(min1, s[i]);
  }
  
  vector<vector<int> > p = perm_group(s);

  int ans = 0;
  for(int i = 0; i < p.size(); i++){
    if(p[i].size() == 1) continue;

    int min2 = INF;
    int sum = 0;
    for(int j = 0; j < p[i].size(); j++){
      sum += s[p[i][j]];
      min2 = min(min2, s[p[i][j]]);
    }
    ans += min(sum - min2 + (p[i].size() - 1) * min2, 
	       sum + min2 + (p[i].size() + 1) * min1);
  }
  printf("%d\n", ans);
  return 0;
}