题目描述

Kruskal算法是最小生成树的经典算法，其步骤为：
E1：将所有的边按权值排序；
E2：设每个顶点为一个独立的点集，生成树T为空集；
E3：依序扫描每一条边，直到已输出n-1条边：
E31：若vi、vj不在同一点集中，则将该边加入生成树T中，并合并这两个点集；否则舍弃该边；
本题要求读入带权图，对其所有边按权值排序后输出。

输入格式

输入为邻接矩阵存储的图，第一行为正整数n（小于100），表示图中顶点个数
接下来是n行，每行为n个空格隔开的非负整数。0表示两个顶点之间没有直达边，非0表示有直达边。且该数字为对应直达边的权重。

输出格式

对所有边按权重排序后输出。如果图只有1个点（即没有边），则直接输出空行。

输入样例

7
0 10 9 13 0 0 0
10 0 0 15 7 0 12
9 0 0 4 0 3 0
13 15 4 0 0 22 23
0 7 0 0 0 0 20
0 0 3 22 0 0 32
0 12 0 23 20 32 0

输出样例  

<2,5>:3
<5,2>:3
<3,2>:4
<2,3>:4
<4,1>:7
<1,4>:7
<2,0>:9
<0,2>:9
<1,0>:10
<0,1>:10
<1,6>:12
<6,1>:12
<0,3>:13
<3,0>:13
<1,3>:15
<3,1>:15
<4,6>:20
<6,4>:20
<3,5>:22
<5,3>:22
<6,3>:23
<3,6>:23
<5,6>:32
<6,5>:32

数据范围与提示

注意题目的测试数据构造时用的排序算法如下：
for(int i=0;i    for(int j=i+1;j         if(a[j]

代码展示 

#include
#include
using namespace std;struct side{int row;int col;int weight;
};struct allSides{int num;side * sides;
};bool operator <(const side &side1,const side &side2){return side1.weight>n;allSides sss;sss.num=n*n;sss.sides=new side[n*n];int matrix[n][n];for(int i=0;i>matrix[i][j];}if(n==1){cout<:"<:"<