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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
| #include<bits/stdc++.h>
using namespace std; const int N = 1000005; #define int long long int n, m, h[N], fa[N], maxn, ans, cnt, sum, num; bool vis[N];
int find(int x) { if (fa[x] != x) fa[x] = find(fa[x]); return fa[x]; }
void merge(int x, int y) { x = find(x); y = find(y); if (x != y) fa[y] = x; }
struct node { int to, next, dis; } e[N << 2]; struct edge { int st, ed, dis; } ed[N << 2];
int head[N], tmp;
void add(int x, int y, int z) { e[++tmp].to = y; e[tmp].next = head[x]; e[tmp].dis = z; head[x] = tmp; }
void dfs(int cur) { vis[cur] = true; maxn++; for (int i = head[cur]; i; i = e[i].next) { int v = e[i].to; ed[++cnt].st = cur; ed[cnt].ed = v; ed[cnt].dis = e[i].dis; if (vis[v]) continue; dfs(v); } }
bool cmp(edge x, edge y) { if (h[x.ed] == h[y.ed]) return x.dis < y.dis; return h[x.ed] > h[y.ed]; }
int read() { int s = 0, w = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') w = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = (s << 1) + (s << 3) + ch - '0'; ch = getchar(); } return s * w; }
signed main() { n = read(), m = read(); for (int i = 1; i <= n; i++) { h[i] = read(); fa[i] = i; } for (int i = 1; i <= m; i++) { int u = read(), v = read(), t = read(); if (h[u] >= h[v]) add(u, v, t); if (h[u] <= h[v]) add(v, u, t);
} dfs(1); cout << maxn << " "; sort(ed + 1, ed + cnt + 1, cmp); for (int i = 1; i <= cnt; i++) { if (find(ed[i].st) != find(ed[i].ed)) { merge(ed[i].st, ed[i].ed); ans += ed[i].dis; } } cout << ans << endl; return 0; }
|