#P4960. cwbc的独立集
cwbc的独立集
cwbc 的独立集
题目描述
cwbc 正在研究一张带权无向图。一个边独立集由若干条两两不共享端点的边组成。首先求边独立集的最大边数,再在所有达到这个边数的边独立集中,求最大边权与最小边权之差的最小值。
输入格式
第一行两个正整数 ,表示点数和边数。
接下来 行,每行三个正整数 ,表示连接 、权值为 的无向边。
,,,图中无重边和自环。
输出格式
第一行输出最大边独立集的边数。第二行输出题目所求的最小权值差。
样例
4 4
1 2 1
3 4 7
2 3 2
1 4 6
2
4