问题 1058. -- 找子图

1058: 找子图

时间限制:1000 ms 内存限制:128 MB
提交:48 解决:32
[ 提交][ 状态][ 讨论版]

题目描述

现有一张无向图，有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

来源

2015西电ACM校赛

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