[HOJ]21 大象

先考慮個別的循環節
並且以該循環節的最小值mn當作調換的點
求出調換該循環節所有點所花費的值

令所有點中的最小值為mm
枚舉所有循環節
如果在mm和mn調換後會有更佳解
則更新值

#include<cstdio>
#include<vector>
#define MAX 1000005
#define INF 1000000000
using namespace std;
struct node{
    int m,l;
};
vector<node> e;
int v[MAX],a[MAX],b[MAX],nt[MAX];
int n,siz,mn,mm=INF;
long long ans,val;
bool vis[MAX];
void dfs(int k){
    siz++;
    val+=v[k];
    vis[k]=true;
    if(mn>v[k])mn=v[k];
    if(!vis[nt[k]])dfs(nt[k]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);
        nt[a[i]]=b[i];
    }
    for(int i=1;i<=n;i++){
        if(v[i]<mm)mm=v[i];
        if(!vis[i]){
            mn=INF;
            siz=val=0;
            dfs(i);
            ans+=val+mn*(siz-2);
            e.push_back(node{mn,siz});
        }
    }
    for(int i=0;i<e.size();i++){
        if(e[i].m*(e[i].l-1)>e[i].m*2+mm*2+mm*(e[i].l-1))
            ans-=e[i].m*(e[i].l-1)-e[i].m*2-mm*2-mm*(e[i].l-1);
    }
    printf("%lld\n",ans);
}