很早之前就看过这题，思路题把，确实挺难想的，黑书248页有讲解。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 int p[10001]; 8 struct node 9 { 10 int id; 11 int x; 12 int pos; 13 }num[10001]; 14 int flag[10001],minz; 15 int cmp1(node a,node b) 16 { 17 return a.x < b.x; 18 } 19 int cmp2(node a,node b) 20 { 21 return a.id < b.id; 22 } 23 int judge(int x) 24 { 25 int res = 0,m,temp = 0; 26 if(x == num[x].pos) 27 { 28 flag[x] = 1; 29 return 0; 30 } 31 m = num[x].x; 32 while(!flag[x]) 33 { 34 flag[x] = 1; 35 temp += num[x].x; 36 x = num[x].pos; 37 m = min(m,num[x].x); 38 res ++; 39 } 40 return temp + min((res-2)*m,m+(res+1)*minz); 41 } 42 int main() 43 { 44 int n,i,sum; 45 scanf("%d",&n); 46 minz = 100000000; 47 sum = 0; 48 for(i = 1;i <= n;i ++) 49 { 50 scanf("%d",&num[i].x); 51 minz = min(num[i].x,minz); 52 num[i].id = i; 53 } 54 sort(num+1,num+n+1,cmp1); 55 for(i = 1;i <= n;i ++) 56 { 57 num[i].pos = i; 58 } 59 sort(num+1,num+n+1,cmp2); 60 for(i = 1;i <= n;i ++) 61 { 62 if(!flag[i]) 63 { 64 sum += judge(i); 65 } 66 } 67 printf("%d ",sum); 68 return 0; 69 }