要专门使用一个广搜判断可以拓展到的点
```
#include <cstdio>
#include <queue>
#include <algorithm>
#define ll long long
template <typename T>
inline void read(T &t) {
t = 0;
T a = 1;
char ch = getchar();
while (ch < 48 || ch > 57) {
if (ch == '-')
a = -1;
ch = getchar();
}
while (ch >= 48 && ch <= 57) {
t = (t << 1) + (t << 3) + (ch ^ 48);
ch = getchar();
}
t *= a;
}
template <typename T, typename... Args>
inline void read(T &tmp, Args &...tmps) { read(tmp); read(tmps...); }
using namespace std;
const int N = 1e5 + 5, M = 1e6 + 5;
int n, m, h[N], fa[N], tot, head[N], cnt, s;
ll MST;
bool vis[N];
struct Edge {
int u, v, h;
ll w;
bool operator < (Edge X) const { return h == X.h ? w < X.w : h > X.h; }
} edge[M << 1];
struct node {
ll w;
int to, next;
} x[M << 1];
queue<int> q;
inline void add(int u, int v, ll w) {
x[++tot].w = w, x[tot].to = v;
x[tot].next = head[u], head[u] = tot;
}
inline void bfs() {
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
if (!vis[u])
s++, vis[u] = true;
else
continue;
for (int i = head[u]; i; i = x[i].next) {
int v = x[i].to;
ll w = x[i].w;
edge[++cnt].h = h[v], edge[cnt].u = u, edge[cnt].v = v, edge[cnt].w = w;
q.push(v);
}
}
}
inline int FindSet(int x) {
if (x == fa[x])
return x;
return fa[x] = FindSet(fa[x]);
}
inline void kruskal() {
sort(edge + 1, edge + cnt + 1);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1, j = 0; i <= cnt; i++) {
int a = FindSet(edge[i].u), b = FindSet(edge[i].v);
if (a == b)
continue;
fa[a] = b;
MST += edge[i].w;
j++;
if (j >= s - 1)
return ;
}
}
int main() {
read(n, m);
for (int i = 1; i <= n; i++)
read(h[i]);
for (int i = 1, a, b; i <= m; i++) {
ll c;
read(a, b, c);
if (h[a] >= h[b])
add(a, b, c);
if (h[a] <= h[b])
add(b, a, c);
}
bfs();
kruskal();
printf("%d %lld\n", s, MST);
return 0;
}
```
by _zhy @ 2022-10-03 13:29:27
@[钟浩洋](/user/476921) 但是我用的是 Prim，不是 Kruskal，Prim 本身就类似广搜，一层层扩展吧。
by NightTide @ 2022-10-03 13:56:41