牛客练习赛69 C

题意： 给定 n n n点 m m m边，让你确定一个大小为 n n n的排列使得 ∑ i = 2 n d i s ( a i − 1 , a i ) \sum_{i=2}^n dis(a_{i-1},a_i) ∑i=2n​dis(ai−1​,ai​)最大。
数据范围： 1 ≤ m ≤ 5 × 1 0 5 , 1 ≤ u , v ≤ n , 1 ≤ w ≤ 1 0 9 1\leq m\leq 5\times 10^5, 1\leq u,v\leq n, 1\leq w\leq 10^9 1≤m≤5×105,1≤u,v≤n,1≤w≤109，保证图是联通的

题解： 本题考虑一个问题，即要想求图中两点的所有路径中的最大值，那么我们在选择排列的时候，就从边权最大的开始递减构造，将这两个点放一块，那么这两个点就一定是选择边权当前可选择的最大值了。这里就想到了生成树，构造一个最大生成树即可。

题解：

#include<bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
const int M = N << 1;
int n, m;

struct Node{
	int a, b, c;
	bool operator < (const Node &A) const {
		return c > A.c;
	}
}p[N];

int f[N];
int find(int x) {
	if(x != f[x]) f[x] = find(f[x]);
	return f[x];
} 

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) f[i] = i;
	for(int i = 1; i <= m; i++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		p[i] = {a, b, c};
	} 
	
	sort(p + 1, p + m + 1);
	long long res = 0;
	for(int i = 1; i <= m; i++) {
		int a = p[i].a, b = p[i].b, c = p[i].c;
		a = find(a), b = find(b);
		if(a != b) {
			f[a] = b;
			res += c;
		}
	}
	
	printf("%lld\n", res);
	
	return 0;
}