很早之前就看过这题，思路题把，确实挺难想的，黑书248页有讲解。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int p[];
struct node
{
int id;
int x;
int pos;
}num[];
int flag[],minz;
int cmp1(node a,node b)
{
return a.x < b.x;
}
int cmp2(node a,node b)
{
return a.id < b.id;
}
int judge(int x)
{
int res = ,m,temp = ;
if(x == num[x].pos)
{
flag[x] = ;
return ;
}
m = num[x].x;
while(!flag[x])
{
flag[x] = ;
temp += num[x].x;
x = num[x].pos;
m = min(m,num[x].x);
res ++;
}
return temp + min((res-)*m,m+(res+)*minz);
}
int main()
{
int n,i,sum;
scanf("%d",&n);
minz = ;
sum = ;
for(i = ;i <= n;i ++)
{
scanf("%d",&num[i].x);
minz = min(num[i].x,minz);
num[i].id = i;
}
sort(num+,num+n+,cmp1);
for(i = ;i <= n;i ++)
{
num[i].pos = i;
}
sort(num+,num+n+,cmp2);
for(i = ;i <= n;i ++)
{
if(!flag[i])
{
sum += judge(i);
}
}
printf("%d\n",sum);
return ;
}