【题解】LuoGu2573： [SCOI2012]滑雪

原题传送门
时间胶囊是个好东西，这有一些奇怪的性质

首先考虑建图，在输入的边的基础上，如果高度不同，高的往低的连一条单向边；如果高度相同，连一条双向边
然后考虑求最多到达的点个数，由于我们拥有时间胶囊，所以直接从1开始bfs，遍历到的点都是可以走到的，感性理解一下
最后考虑求最短距离，用kruskal即可，用到的边在bfs时加进去，排序有技巧，需要以一条边终点高度为第一关键字，边长为第二关键字排序，保证正确性

Code：

#include <bits/stdc++.h>
#define maxn 100010
#define maxm 2000010
#define int long long
using namespace std;
struct Edge{
	int to, next, len;
}edge[maxm];
struct Line{
	int x, y, len;
}a[maxm];
int n, m, head[maxn], num, h[maxn], f[maxn], cnt, ans, vis[maxn];
queue <int> q;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge) { y, head[x], z }; head[x] = num; }
bool cmp(Line x, Line y){ return h[x.y] == h[y.y] ? x.len < y.len : h[x.y] > h[y.y]; }
int get(int k){ return k == f[k] ? k : f[k] = get(f[k]); }

void bfs(){
	q.push(1);
	vis[1] = 1;
	while (!q.empty()){
		int u = q.front(); q.pop();
		for (int i = head[u]; i; i = edge[i].next){
			int v = edge[i].to;
			a[++cnt] = (Line) { u, v, edge[i].len };
			if (!vis[v]) ++ans, vis[v] = 1, q.push(v);
		}
	}
}

signed main(){
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) h[i] = read();
	for (int i = 1; i <= m; ++i){
		int x = read(), y = read(), z = read();
		if (h[x] >= h[y]) addedge(x, y, z);
		if (h[x] <= h[y]) addedge(y, x, z);
	}
	bfs();
	printf("%lld ", ans + 1);
	ans = 0;
	sort(a + 1, a + 1 + cnt, cmp);
	for (int i = 1; i <= n; ++i) f[i] = i;
	for (int i = 1; i <= cnt; ++i){
		int s1 = get(a[i].x), s2 = get(a[i].y);
		if (s1 != s2) f[s1] = s2, ans += a[i].len;
	}
	printf("%lld\n", ans);
	return 0;
}