Cow Sorting(置换）

http://poj.org/problem?id=3270

// File Name: poj3270.cpp// Author: bo_jwolf// Created Time: 2013年10月09日 星期三 17:19:00#include<vector>#include<list>#include<map>#include<set>#include<deque>#include<stack>#include<bitset>#include<algorithm>#include<functional>#include<numeric>#include<utility>#include<sstream>#include<iostream>#include<iomanip>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#include<ctime>using namespace std;const int maxn = 1000005;struct node{int cnt, val;}a[ maxn ];int tot, t[ maxn ], m[ maxn ], sum, Min = 1, n;bool flag[ maxn ];void dfs( int u ){for( int i = 0; i < n; ++i ){if( !flag[ i ] && t[ i ] == u ){a[ tot ].cnt++;flag[ i ] = true;a[ tot ].val = min( a[ tot ].val, t[ i ] );dfs( m[ i ] );}}}int main(){while( scanf( "%d", &n ) != EOF ){sum = 0, Min = 1 << 30; for( int i = 0; i < n; ++i ){scanf( "%d", &m[ i ] );t[ i ] = m[ i ];sum += m[ i ];Min = min( Min, m[ i ] );}sort( m, m + n );tot = 0;for( int i = 0; i < n; ++i ){if( flag[ i ] )continue;a[ tot ].val = t[ i ];a[ tot ].cnt = 1;flag[ i ] = true;dfs( m[ i ] );tot++;}for( int i = 0; i < tot; ++i ){sum += min( a[ i ].val * ( a[ i ].cnt - 2 ), a[ i ].val + Min * ( a[ i ].cnt + 1 ) );}printf( "%d\n", sum );}return 0;}