【数据范围】
对于30%的数据，保证 1<=N<=2000
对于100%的数据，保证 1<=N<=100000
对于所有的数据，保证 1<=M<=1000000，1<=Hi<=1000000000，1<=Ki<=1000000000。
首先不考虑高度这就是个裸的最小生成树加入了高度就不能直接做，比如下面这样：
直接做显然会选两条1的边
加入高度后就按终点高度为第一关键字排序保证下来的每个点都能走到即可
代码如下：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #include<bitset> #include<set> #define ll long long #define mp(x,y) make_pair(x,y) #define pll pair<long long,long long> #define pii pair<int,int> using namespace std; inline ll read() { ll f=1,x=0;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int stack[20]; inline void write(int x) { if(x<0){putchar(‘-‘);x=-x;} if(!x){putchar(‘0‘);return;} int top=0; while(x)stack[++top]=x%10,x/=10; while(top)putchar(stack[top--]+‘0‘); } inline void pr1(int x){write(x);putchar(‘ ‘);} inline void pr2(int x){write(x);putchar(‘\n‘);} int n,m; int fa[110000]; int findfa(int x) { if(fa[x]!=x)fa[x]=findfa(fa[x]); return fa[x]; } struct node{ int x,y,next;ll d; }a[2100000];int len,last[210000]; 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; } int v[210000]; int h[210000],tot; void dfs(int x) { v[x]=1;tot++; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(!v[y])dfs(y); } } bool cmp(node a,node b) { if(h[a.y]!=h[b.y])return h[a.y]>h[b.y]; return a.d<b.d; } int main() { n=(int)read(),m=(int)read(); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=n;i++)h[i]=read(),fa[i]=i; for(int i=1;i<=m;i++) { int x,y;ll d; x=(int)read(),y=(int)read(),d=read(); if(h[x]>h[y])ins(x,y,d); else ins(y,x,d); if(h[x]==h[y])ins(x,y,d); } memset(v,0,sizeof(v)); tot=0;dfs(1);ll ans=0ll; printf("%d ",tot); sort(a+1,a+len+1,cmp); for(int i=1;i<=len;i++) { int x=a[i].x,y=a[i].y; if(!v[x]||!v[y])continue; int fx=findfa(x),fy=findfa(y); if(fx!=fy) { fa[fx]=fy; ans+=a[i].d; } } printf("%lld\n",ans); return 0; }
原文：https://www.cnblogs.com/MT-LI/p/10531473.html