E - QS Network
思路：最小生成树，数组不要开小了。
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define MAXN 100010using namespace std;int t,n,tot,sum,ans;int fa[MAXN],mon[MAXN];struct nond{ ???int x,y,z;}v[1000050];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=1;i<=n;i++) ???scanf("%d",&mon[i]); ???????for(int i=1;i<=n;i++) ???????????for(int j=1;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+1,v+1+tot,cmp); ???????for(int i=1;i<=n;i++) ???fa[i]=i; ???????for(int i=1;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-1) ???break; ???????} ???????cout<<ans<<endl;ans=0;sum=0;tot=0; ???}}E - QS Network
原文地址：https://www.cnblogs.com/cangT-Tlan/p/8461186.html