23
2011
05

C++最小生成树问题

问题描述

求一个连通无向图的最小生成树的代价(图边权值为正整数)。

输入

第一行是一个整数N(1<=N<=20),表示有多少个图需要计算。以下有N个图,第i图的第一行是一个整数M(1<=M<=50),表示图的顶点数,第i图的第2行至1+M行为一个M*M的二维矩阵,其元素ai,j表示图的i顶点和j顶点的连接情况,如果ai,j=0,表示i顶点和j顶点不相连;如果ai,j>0,表示i顶点和j顶点的连接权值。

输出

«1»