#P4960. cwbc的独立集

    ID: 4059 传统题 1000ms 512MiB 尝试: 22 已通过: 9 难度: 9 上传者: 标签>难度分类省选/NOI-图论Blossom 算法排序与序列处理尺取法增广路模拟与实现技巧增量维护CF2700By

cwbc的独立集

cwbc 的独立集

题目描述

cwbc 正在研究一张带权无向图。一个边独立集由若干条两两不共享端点的边组成。首先求边独立集的最大边数,再在所有达到这个边数的边独立集中,求最大边权与最小边权之差的最小值。

输入格式

第一行两个正整数 n,mn,m,表示点数和边数。

接下来 mm 行,每行三个正整数 xi,yi,wix_i,y_i,w_i,表示连接 xi,yix_i,y_i、权值为 wiw_i 的无向边。

1≤n≤1201\le n\le120,1≤m≤n(n−1)/21\le m\le n(n-1)/2,1≤wi≤1091\le w_i\le10^9,图中无重边和自环。

输出格式

第一行输出最大边独立集的边数。第二行输出题目所求的最小权值差。

样例

4 4
1 2 1
3 4 7
2 3 2
1 4 6
2
4