题解 | #How to sort#

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<unordered_map>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int N=2010,MOD=998244353,INF=0x7f7f7f7f;
// unordered_map<int,int>mp;
map<int,int>mp;

struct NODE{
    int x,idx;
    bool operator<(const NODE& o) const{
        return x<o.x;
    }
}a[N];
int n;
int fa[N],val[N],tot[N];
int find(int u){
    return fa[u]==u?u:fa[u]=find(fa[u]);
}

void solve(){
    cin>>n;
    int minn=1;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        a[i]={x,i};
        fa[i]=i;
        val[i]=x;
        tot[i]=1;
        if(a[i].x<a[minn].x) minn=i;
    }
    minn=a[minn].x;
    sort(a+1,a+1+n);
    
    // for(int i=1;i<=n;i++){
    //     cout<<a[i].x<<' '<<a[i].idx<<endl;
    // }
    
    LL res=0;
    for(int i=1;i<=n;i++){
        if(a[i].idx==i) continue;
        int u=a[i].idx;
        int v=a[u].idx;
        int fu=find(u),fv=find(v);
        if(fu!=fv){
            val[fv]=min(val[fv],val[fu]);
            tot[fv]=tot[fu]+tot[fv];
            fa[fu]=fv;
        }
        res+=a[i].x;
    }
    
    // for(int i=1;i<=n;i++){
    //     cout<<fa[i]<<' '<<val[i]<<' '<<tot[i]<<endl;
    // }
    
    
    for(int i=1;i<=n;i++){
        if(fa[i]==i&&tot[i]>=2){
            // cout<<i<<' '<<tot[i]<<endl;
            //两种情况 1.并查集内部换n-1次  2.先和整个序列里最小的x换，再用x换n-1次，再换回来
            res+=min( val[i]*(tot[i]-2),minn*(tot[i]+1)+val[i]);

        }
    }
    cout<<res<<endl;
    
    
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0);

    int t;
    // cin>>t;
    t=1;
    while(t--) solve();
    
    return 0;
}