生成树

mac2025-03-04  4

生成树

时间限制:2sec / 空间限制:256MB

题意

给出一个包含 n n n个点, m m m条有权边的无向图,请你求出这个图的最小生成树以及次小生成树的权值。

最小生成树是一副连通加权无向图中一棵权值最小的生成树。次小生成树则是一副连通加权无向图中一棵权值第二小的生成树。

最小生成树的权值可能与次小生成树相同。

输入

第一行两个整数 n n n m m m,表示点的个数和边的个数,用一个空格分隔;

接下来 m m m行,每行3个整数 a , b , w a,b,w a,b,w,表示一条边,每两个整数之间用一个空格分隔;

满足 2 < = n < = 1 0 5 , 1 < = m < = 1 0 5 , 1 < = a , b < = n , 1 < = w < = 10000 2 <= n <= 10^5,1 <= m <= 10^5,1 <= a,b<= n,1 <= w <= 10000 2<=n<=105,1<=m<=105,1<=a,b<=n,1<=w<=10000

数据保证输入的图是连通图。

输出

两个整数,第一个整数表示这个图的最小生成树的权值,第二个整数表示这个图的次小生成树的权值,两个整数之间用一个空格分隔。

样例1

###输入

3 3

1 2 2

2 3 2

1 3 2

输出

4 4

样例2

输入

3 3

1 2 1

2 3 2

1 3 1

输出

2 3

最新回复(0)