SCOI2012 滑雪与时间胶囊

发表于 更新于 分类于

「SCOI2012」滑雪与时间胶囊

因为只能从更高的点到不高于它的点。

我们给边定向后(虽然有些边还是无向的)，看一下从\(1\)能到哪些点就。

第二问，因为有些边是有向的，为了走完所有点，一点要从更高的点开始走。

如果形成了树的结构，显然是可以走完所有点的。

但是为了保证从高点走到低点，我们需要指向更高点的边被优先选出。

不然有可能没有走向它的边，肯定是不对的。

话说这图好像可以叉掉\(prime\)。

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
53
54
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e6 + 6;
struct node {
	int nxt, v, w;
} e[N << 1];
struct Edge {
	int u, v, w;
} E[N << 1];
int n, m, h[N], head[N], ecnt, cnt, tot, fa[N];

int find(int x) {return fa[x] ? fa[x] = find(fa[x]) : x;}
void add-edge(int u, int v, int w) {
    e[++ecnt] = {head[u], v, w}; head[u] = ecnt;
    e[++ecnt] = {head[v], u, w}; head[v] = ecnt;
}

bool vis[N];
void dfs(int u) {
	if (vis[u]) return;
	tot++;
	vis[u] = 1;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].v, w = e[i].w;
		if (h[u] < h[v]) continue;
        E[++cnt] = {u, v, w};
		dfs(v);
	}
}

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= m; i++) {
    	int u, v , w;
    	cin >> u >> v >> w;
    	add-edge(u, v, w);
    }
    dfs(1);
    sort(E + 1, E + cnt + 1, [&](Edge a, Edge b) {return (h[a.v] == h[b.v]) ? a.w < b.w : h[a.v] > h[b.v];});
    int c = 0, w = 0;
    for (int i = 1; i <= cnt; i++) {
        int u = find(E[i].u), v = find(E[i].v);
        if (u == v) continue;
        c++;
        w += E[i].w;
        fa[u] = v;
        if (c == n - 1) break;
    }
    cout << tot << " " << w << endl;
    return 0;
}