[cpp] /*Template*/ /*Poj 3270 Cow Sorting */ #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> #include <cassert> #include <cctype> #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> using namespace std; const double EPS = 1e-8; const int MAXN = 10005; const int INF = 1<<30; const int MOD = 99991; #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) //typedef long long LL; typedef __int64 LL; int gcd(int a,int b){return b?gcd(b,a%b):a;} int n,tot=0; int a[MAXN],b[MAXN]; bool flag[MAXN]; struct rpt { int cnt; //循環節個數 int min; }c[MAXN]; /*int find(int x) { int l=0,r=n,m; while(l<r) { m=l+(r-l)/2; if(x==b[m]) return m; if(x<b[m]) r=m; else l=m+1; } }*/ void Polya(int x) //DFS找循環節 { for(int i=0;i<n;i++) { if(b[i]==x && flag[i]==false) { flag[i]=true; c[tot].cnt++; c[tot].min = min(c[tot].min,a[i]); Polya(a[i]); } } } int main() { // freopen("in.txt","r",stdin); // freopen("out.txt,"w",stdout); cin>>n; tot=0; int i,amin=INF,sum=0; memset(flag,false,sizeof(flag)); for(i=0;i<n;i++) { cin>>a[i]; b[i]=a[i]; sum+=a[i]; amin = min(amin,a[i]); } sort(b,b+n); for(i=0;i<n;i++) { if(!flag[i]) { c[tot].cnt=1; c[tot].min=a[i]; flag[i]=true; Polya(a[i]); tot++; } } www.2cto.com for(i=0;i<tot;i++) sum+=min(c[i].min*(c[i].cnt-2),amin*(c[i].cnt+1)+c[i].min); cout<<sum<<endl; /*for(i=0;i<tot;i++) { cout<<c[i].cnt<<" "<<c[i].min<<endl; }*/ return 0; } 無聊貼個代碼 置換群用DFS實現,分別記錄置換最小值和置換的元素個數就好了 在置換中最小的元素分別和別的元素置換就是最優解了 但注意有可能是整個數組中最小的元素進行交換,進行一次比較取最小值就行了 知道是置換但是後面的那個坑點還真沒想到呢... 看題解才AC的捂臉...
