【图论训练】天气晴朗的魔法【最小生成树】

思路：

因为是最大值要最小，所以直接先跑一遍最小生成树，然后跑出最大的那条边。
然后让总和最大，直接从那条边往前跑，跑最大的。

$code$

#include
#include
#include

#define ll long long

using namespace std;

const int MAXN = 2e5 + 10;

int n, m, fa[MAXN];
struct node {
	int from, to, w;
}b[MAXN << 1];

bool cmp(node x, node y) {
	return x.w < y.w;
}

int find_(int x) {
	if(x == fa[x]) return x;
	return fa[x] = find_(fa[x]);
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) fa[i] = i;
	for(int i = 1; i <= m; i ++)
		scanf("%d%d%d", &b[i].from, &b[i].to, &b[i].w);
	sort(b + 1, b + 1 + m, cmp);
	int tmp = 0, p = 0;
	for(int i = 1; i <= m; i ++) {
		int x = find_(b[i].from), y = find_(b[i].to);
		if(x != y) fa[x] = y, tmp ++;
		if(tmp == n - 1) {
			p = i;
			while(b[p].w == b[i].w && p <= m) p ++;
			p --;
			break;
		}
	}
	tmp = 0;
	ll ans = 0;
	for(int i = 1; i <= n; i ++) fa[i] = i;
	for(int i = p; i >= 1; i --) {
		int x = find_(b[i].from), y = find_(b[i].to);
		if(x != y) fa[x] = y, tmp ++, ans += b[i].w;
		if(tmp == n - 1) break;
	}
	printf("%lld", ans);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52