```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
const int M = 1e6 + 10;
int n,m,u,v,w,ans,cnt,sum,h[N],fa[N],head[M],r,l,top;
bool vis[N];
struct node
{
int v,w;
node(int v,int w) : v(v),w(w) {}
};
vector<node> e[1000012];
struct Node
{
int u,v,w;
}new_edge[M];
struct path
{
int v,dis;
// bool operator < (const path &other) const {return dis > other.dis;}
path(register int v,register int dis) : v(v),dis(dis) {}
};
queue<path> q;
void build(int u,int v,int w)
{
e[u].push_back(node(v,w));
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unity(int x,int y)
{
x = find(x),y = find(y);
if(x != y) fa[x] = y;
}
inline int read()
{
register char in = getchar(),f = 0;register int t = 0;
for(;!isdigit(in);in = getchar())if(!(in ^ 45)) f = 1;
for(;in >= '0' && in <= '9';in = getchar())
t = (t << 1) + (t << 3) + (in ^ 48);
return f ? -t : t;
}
inline void write(register long long x)
{
static int t[25];register int tp = 0;
if(x == 0) return (void) (puts("0"));
else if(x < 0) putchar('-'),x = -x;
while(x) t[++tp] = x % 10,x /= 10;
while(tp) putchar(t[tp--] + '0');
puts("");
}
bool cmp(Node a,Node b)
{
if(h[a.v] != h[b.v]) return h[a.v] >= h[b.v];
return a.w < b.w;
}
void bfs()
{
q.push(path(1,0)),vis[1] = 1;
while(!q.empty())
{
int now = q.front().v; q.pop();
for(int i = 0;i < e[now].size();i++)
{
new_edge[++cnt].u = now,new_edge[cnt].v = e[now][i].v,new_edge[cnt].w = e[now][i].w;
if(!vis[e[now][i].v]) sum++,q.push(path(new_edge[cnt].v,new_edge[cnt].w)),vis[e[now][i].v] = 1;
}
}
}
#define stdi stdin
#define stdo stdout
signed main()
{
setvbuf(stdi,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
setvbuf(stdo,(char*)calloc(1 << 20,sizeof(char)),_IOFBF,1 << 20);
n = read(),m = read();
for(int i = 1;i <= n;i++) fa[i] = i,h[i] = read();
for(int i = 1;i <= m;i++)
{
u = read(),v = read(),w = read();
if(h[u] >= h[v]) build(u,v,w);
if(h[u] <= h[v]) build(v,u,w);
}
bfs();
sort(new_edge + 1,new_edge + 1 + cnt,cmp);
for(int i = 1;i <= cnt;i++)
{
register int u = find(new_edge[i].u);
register int v = find(new_edge[i].v);
if(u != v)fa[u] = v,ans += new_edge[i].w;
}
printf("%lld %lld",sum + 1,ans);
}
```
ok,了
by tjtdrxxz @ 2024-03-23 16:59:07
嗨嗨嗨,醒一醒
by tjtdrxxz @ 2024-03-25 21:28:00