题目链接：
ZOJ 1586 QS Network
题意：
题目比较难懂。有n个点，每个点有一个权值，然后给出这n个点两两之间边的权值，
但是如果a和b直接连通的话总共的权值是边的权值加上a，b两点的权值。
问将这n个点全部连通的最小权值和。
分析：
在读边的时候只需要将边的权值重新考虑下:i->j：if(i!=j) w+=val[i]+val[j];
然后直接用Kruskal就行了。
CODE :
//14460K 60MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=1100;int n,ans,tot,m,u,v,w,T;
int pre[maxn],val[maxn];struct Edge{int u,v,w;
}edge[maxn*maxn];void init()
{ans=tot=0;for(int i=0;i<maxn;i++)pre[i]=i;
}bool cmp(struct Edge a,struct Edge b)
{return a.w<b.w;
}int find(int x)
{return pre[x]==x?x:pre[x]=find(pre[x]);
}int main()
{
#ifdef LOCALfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);
#endifscanf("%d",&T);while(T--){scanf("%d",&n);init();for(int i=1;i<=n;i++)scanf("%d",&val[i]);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w);if(i!=j) w+=val[i]+val[j];edge[tot].u=i;edge[tot].v=j;edge[tot].w=w;tot++;}}sort(edge,edge+tot,cmp);for(int i=0;i<tot;i++){u=edge[i].u;v=edge[i].v;w=edge[i].w;int fu=find(u);int fv=find(v);//printf("u=%d fu=%d v=%d fv=%d\n",u,fu,v,fv);if(fu!=fv){pre[fu]=fv;ans+=w;}}printf("%d\n",ans);}return 0;
}