【题解】Destruction

题目：Destruction

题意：

给定一个无序图，我们可以删除任意条边，我们获得删除边的权值，要求最后图仍是连通图。问获得的数最大是多少？

思路：

• 估计大家一眼就看出是最小生成树。 我的24k dog眼还是太laji了，第一眼根本看不出来。
• 思路还是最小生成树没有问题，但是没有必要真的去建立一棵树。
• 我们可以用并查集的思想，将这棵树看做一个集合：所有连通的点视为一个集合，当所有点都在一个集合中时，最小生成树也就建好了。
• 首先将所有大于0的权值求和（负数边我们可以将其留在树上，因为删去只会使得总和更小）得到sum，之后将所有边按照权值排序，遍历所有边，如果第i条边的左右两个点没有连通，就连通两个点（划入一个集合）并根绝权值判断sum是否减去其权值。
• 最后sum就是结果。记得用long long。 不知道在long long上吃多少亏了…

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
const int N = 2e5 + 10;
//c, {x, y}
typedef pair<int ,pair<int,int>> PIII;
typedef long long ll;

int h[N];
vector<PIII>p;

int find(int x)
{
	if (h[x] == x)return x;
	return h[x] = find(h[x]);
}

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; ++i)h[i] = i;

	ll sum = 0;
	for (int i = 0; i < m; ++i)
	{
		int x, y, c;
		cin >> x >> y >> c;
		if (c > 0)sum += c;
		p.push_back({ c,{x, y} });
	}

	sort(p.begin(), p.end());

	//for (int i = 0; i < m; ++i)	cout << p[i].first << " " << p[i].second.first << " " << p[i].second.second << endl;

	for (int i = 0; i < m; ++i)
	{
		int a = find(p[i].second.first), b = find(p[i].second.second);
		if (a != b)
		{
			h[a] = b;
			if (p[i].first > 0)sum -= p[i].first;
		}
	}

	cout << sum << endl;
	
	return 0;
}