网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1058. -- 找子图

1058: 找子图

时间限制: 1 Sec  内存限制: 128 MB
提交: 37  解决: 22
[提交][状态][讨论版]

题目描述

现有一张无向图,有n个点m条边,每条边都有一个权值w,现要求从中找出一个子图,这个子图需满足以下特征:
1.子图可以为空。
2.若某条边的两个端点都在此子图中,则这条边在这个子图中。
3.若某条边的两个端点都不在此子图中,则这条边在这个子图外。
4.若某条边的两个端点一个在子图中,另一个不在,则这条边消失。
5.子图中所有边权值的和减去子图外所有边权值的和最大(不包含消失的边)。
输出这个最大值。

输入

多组数据

对于每组数据,第一行两个整数n,m(1<=n<=100000,1<=m<=500000)
接下来m行,每行三个整数u,v,w,表示在u和v间有一条权值为w的无向边(1<=u,v<=n,-1000<=w<=1000)

输出

 对于每组数据,输出答案。

样例输入

3 3
1 2 2
2 3 -1
1 3 3
2 1
1 2 -1

样例输出

4
1

提示

 注意重边和自环,输入数据较大,请慎用cin/cout

来源

[提交][状态][讨论版]