10 pts kruskal 求调

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+1;
const int maxe=1e5+1;

int fa[maxn];
int n,m;
int ans,e_cnt;

struct edge
{
    int u,v,w,cnt;
}e[maxe];

bool cmp(edge a,edge b){
    return a.w < b.w;
}

int find(int a){
    if(a==fa[a]) return a;
    else{
        fa[a]=find(fa[a]);
        return fa[a];
    }
}

void merge(int a,int b){
    fa[find(a)]=find(b);
}

bool query(int a,int b){
    if(find(a)==find(b)) return 1;
    else return 0;
}

void sset(){
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
}

void init(){
    cin>>n;
    for(int i=1;i<=n;i++){
        e[i].cnt=++e_cnt;
        e[i].u=0;
        e[i].v=i;
        cin>>e[i].w;
    }
    for(int i=1;i<=4;i++){
        for(int j=1;j<=4;j++){
            e[++e_cnt].cnt=e_cnt;
            e[e_cnt].u=i;
            e[e_cnt].v=j;
            cin>>e[e_cnt].w;
        }
    }
}

int main(){

    init();
    sset();

    // for(int i=1;i<=e_cnt;i++){
    //     cout<<"edge cnt:"<<i<<endl;
    //     cout<<"u:"<<e[i].u<<endl;
    //     cout<<"v:"<<e[i].v<<endl;
    //     cout<<"w:"<<e[i].w<<endl;
    //     cout<<endl;
    // }

    sort(e+1,e+1+e_cnt,cmp);

    for(int i=1;i<=e_cnt;i++){
        int u=e[i].u;
        int v=e[i].v;
        int w=e[i].w;
        if(query(u,v)){
            continue;
        }
        merge(u,v);
        ans+=w;
    }
    //连通
    for(int i=1;i<=n-1;i++){
        if(query(i,i+1)) continue;
        cout<<-1<<endl;
        return 0;
    }

    cout<<ans<<endl;

    return 0;
}