E - QS Network

E - QS Network

思路：最小生成树，数组不要开小了。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 100010

using namespace std;

int t,n,tot,sum,ans;

int fa[MAXN],mon[MAXN];

struct nond{

    int x,y,z;

}v[];

int cmp(nond a,nond b){

    return a.z<b.z;

}

int find(int x){

    if(fa[x]==x)    return x;

    else return fa[x]=find(fa[x]);

}

int main(){

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i=;i<=n;i++)    scanf("%d",&mon[i]);

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++){

                int x;scanf("%d",&x);

                v[++tot].x=i;v[tot].y=j;v[tot].z=x+mon[i]+mon[j];

            }

        sort(v+,v++tot,cmp);

        for(int i=;i<=n;i++)    fa[i]=i;

        for(int i=;i<=tot;i++){

            int dx=find(v[i].x);

            int dy=find(v[i].y);

            if(dx==dy)    continue;

            sum++;fa[dy]=dx;

            ans+=v[i].z;

            if(sum==n-)    break;

        }

        cout<<ans<<endl;ans=;sum=;tot=;

    }

}