测试说明
本关的测试过程如下:
平台编译 step5/main.cpp ;
平台运行该可执行文件,并以标准输入方式提供测试输入;
平台获取该可执行文件的输出,然后将其与预期输出对比,如果一致则测试通过;否则测试失败。
输入格式:
输入n e,顶点数 边数
输入一个n×n的一个矩阵表示一个图的邻接矩阵,在带权有向图中,用 32767 代替无穷大。
输出格式:
首先输出krusal,接下来每一行都会输出通过 krusal 算法求得的最小生成树的每一条边与权值,格式为(i,j):w,表示 (i,j)是最小生成树中的一条边,权值为 w ;接着输出prim,然后与 krusal 算法一样,输出通过 prim 算法求得的最小生成树的边及权值。
以下是平台对 step5/main.cpp 的测试样例:
样例输入
6 20
0 6 1 5 32767 32767
6 0 5 32767 3 32767
1 5 0 5 6 4
5 32767 5 0 32767 2
32767 3 6 32767 0 6
32767 32767 4 2 6 0
样例输出
Krusal:
(0,2):1
(3,5):2
(1,4):3
(2,5):4
(1,2):5
Prim:
(0,2):1
(2,5):4
(5,3):2
(2,1):5
(1,4):3