F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4960. -- cwbc的独立集

4960: cwbc的独立集

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 11  Solved: 3
[Submit][Status][Discuss]

Description

cwbc最近在研究无向图,他想要在一个点数为n、边数为m的无向图中找到一个最大的边独立集,但他觉得这样不够
有趣,于是他给每条边一个边权wi,在保证边独立集边数最多的情况下,要求最大权值与最小权值的差最小,但是
cwbc太弱了,只好请大家来帮忙。

Input

第一行两个正整数n、m,n为点数,m为边数。
接下来m行,每行三个正整数xi、yi、wi,表示xi与yi之间有一条边权为wi的无向边。
1<=n<=120, 1<=m<=n*(n-1)/2, 1<=wi<=10^9, 保证不存在重边和自环

Output

第一行一个整数,表示最大边独立集的边数。
第二行一个整数,表示题目要求的最小差值。

Sample Input

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

Sample Output

2
4

HINT

Source

By cwbc

[Submit][Status][Discuss]

HOME Back