这题真的很容易想到最小生成树。
而且题目有特别的性质，高处的连低处的是单向的，但是不会构环（老实讲一开始就是担心这个，但是现在发现好像没啥影响吧），所以其实先把能够访问的点dfs一次，排完序就直接搞好了。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; LL h[1100000]; struct node { int x,y,next;LL d; }a[2100000];int len,last[1100000]; void ins(int x,int y,LL d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } bool v[1100000];int cnt; void dfs(int x) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false) { v[y]=true;cnt++; dfs(y); } } } bool cmp(node n1,node n2) { return (h[n1.y]==h[n2.y])?(n1.d<n2.d):(h[n1.y]>h[n2.y]); } int fa[1100000]; int findfa(int x) { if(fa[x]==x)return x; fa[x]=findfa(fa[x]);return fa[x]; } int main() { int n,m,x,y;LL d; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&h[i]), fa[i]=i; len=0; for(int i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&d); if(h[x]>=h[y])ins(x,y,d); if(h[y]>=h[x])ins(y,x,d); } memset(v,false,sizeof(v)); v[1]=true;cnt=0;dfs(1); sort(a+1,a+len+1,cmp); LL sum=0;int edge=0; for(int k=1;k<=len;k++) { if(v[a[k].x]==true&&v[a[k].y]==true) { int fx=findfa(a[k].x),fy=findfa(a[k].y); if(fx!=fy) { fa[fx]=fy; sum+=a[k].d; edge++; if(edge==cnt)break; } } } printf("%d %lld ",edge+1,sum); return 0; }