自己编写的

#include <iostream> 
#include <algorithm>
const int N = 50;          // 最大顶点个数
using namespace std;
typedef struct edge
{
	int value;           // 边的权值
	int from;            // 边的起始顶点
	int end;             // 边的结束顶点
}Edge;

int set[N];             // 顶点集合
int radio[N];           // 边中顶点的度数，主要用来判断是否分叉
Edge result[N];         // 存放最终结果

/* 查找编号为x的元素属于那个集合并且顺便进行路径压缩 */
int Find_set(int x)
{
    int root,parent;
	
    root = x;
    while(set[root] != root) /* 查找x所在的集合 */
        root = set[root];
	
    parent = set[x];          /* 路径压缩 */
    while(root != parent)
    {
        set[x] = root;
        x = parent;
        parent = set[x];
    }
    return root;
}

/* 合并元素a和元素b所在的两个集合 */
int Union_set(int a,int b)
{
    int root_a = Find_set(a);
    int root_b = Find_set(b);
    set[root_b] = root_a;
	
    return root_a;
}


bool comp(Edge& a,Edge& b)
{
	return (a.value < b.value);
}

int  ShortestLinkedHeuristic(int dis[][N],int n,Edge edge[])
{
	int temp = (n*(n-1))/2;   // 边的个数
	int i;
	int count = 0;
	int k = 0;
	for(i = 0; i < temp; i++)
		if(edge[i].value != 0){  // 保证边的权值不为0，为0代表没有边 
			if((Find_set(edge[i].from) != Find_set(edge[i].end))&&
				radio[edge[i].from] != 2 && radio[edge[i].end] != 2){
					count += edge[i].value;
					radio[edge[i].from]++;
					radio[edge[i].end]++;
					//保存路径
					result[k].value = edge[i].value;
					result[k].from = edge[i].from;
					result[k].end = edge[i].end;
					Union_set(edge[i].from,edge[i].end);
					k++;
					if(k == n -1)
						break;

			}
		}
	return count;
}

int main()
{
	int n;           // 顶点个数
	scanf("%d",&n);
	int i,j;
	int dis[N][N];   // 存放边权值
	for(i = 1; i <= n; i++)
		for(j = 1; j <= n; j++)
			scanf("%d",&dis[i][j]);
	Edge edge[N];      // 存放边的权值，只需要存放下三角
	int cost  = 0;     // 总代价
	int t = 0;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= i-1; j++){
			edge[t].value = dis[i][j];
			if(i < j){
				edge[t].from = i;
				edge[t].end = j;
			}
			else{
				edge[t].from = j;
				edge[t].end = i;
			}
			t++;
		}
	sort(edge,edge+t,comp);             // 对边的权值排序
	for(i = 1; i <= n; i++)
		set[i] = i;
	memset(radio,0,sizeof(radio));
	cost = ShortestLinkedHeuristic(dis,n,edge);
	int end[2];                      // 两个端点
	int x = 0;
	for(i = 1; i <= n; i++)   // 求两个端点
	{
		if(radio[i] == 1)
			end[x++] = i;
	}
	for(i = 0; i < n-1; i++)
		printf("v%d v%d %d\n",result[i].from,result[i].end,result[i].value);
	printf("v%d v%d %d\n",end[0],end[1],dis[end[0]][end[1]]); // 最后两个端点的权值
	printf("%d\n",cost+dis[end[0]][end[1]]);
	return 0;
}