Flymouse is a student of Computer School of Wuhan University. He loves surfing the Internet very much. But his bedroom is outside the campus. After long time thinking, he decides to apply the Internet service. But Flymouse is very poor. He wants to share the connection with his classmates. For the minimum cost, he must pave the shortest lines to connect every computer. Given a list of how much lines it takes to connect each pair of computer, you must find the minimum amount of lines needed to connect them all together. Each computer must connect to some other computers so that a packet can flow from any computer to any other computer. The distance between any two computers will not exceed 100,000.

输入格式

The input includes several cases. The first line contains a single integer t (1 <= t <= 100), the number of test cases. For each case, the first line contains the number of computers, N (3 <= N <= 100). The following N lines contain the N x N matrix, where each element shows the distance from one computer to another. Logically, they are N lines of N space-separated integers. Of course, the diagonal will be 0, since the distance from computer i to itself is not interesting for this problem.

输出格式

For each case, output a single integer that is the sum of the minimum length of lines required to connect the entire set of computers.

样例输入

1 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0

样例输出

28

//最小生成树 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=105,maxm=5000; int matrix[maxn][maxn]; struct bian{ int x,y,c; }; bian u[maxm]; int r[maxm];//边的序号 int p[maxn];//并查集 int n,t; int cmp(const int i,const int j){ return u[i].c<u[j].c; }//间接排序函数 int find(int a){ while(a!=p[a]) a=p[a]; return a; }//并查集的find函数 int main(){ int i,j,m=-1,ans; scanf("%d",&t); while(t--){ scanf("%d",&n); ans=0;m=-1; for(i=0;i<n;i++) for(j=0;j<n;j++) scanf("%d",&matrix[i][j]); for(i=0;i<n;i++) for(j=i+1;j<n;j++){ m++; u[m].x=i; u[m].y=j; u[m].c=matrix[i][j]; } for(i=0;i<n;i++) p[i]=i; for(i=0;i<=m;i++) r[i]=i; sort(r,r+m+1,cmp); for(i=0;i<=m;i++){ int e=r[i]; int x=find(u[e].x); int y=find(u[e].y); //找出当前边两个端点的所在集合编号 if(x!=y){ ans+=u[e].c; p[x]=y;//如果在不同集合，合并 } } printf("%d\n",ans); } return 0; }