分析：直接最大生成树就好了。。至于-1的情况。。 只要没有选出n-1条边都算错。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long ll; int n,m; const int N=1e5+5; struct node { int x,y,z; }a[N]; int f[N]; ll ans; bool cmp(node x,node y) { return x.z>y.z; } inline int get(int x) { if (f[x]==x)return x; else return f[x]=get(f[x]); } int main() { scanf("%d%d",&n,&m); fo(i,1,m)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+1+m,cmp); fo(i,1,n)f[i]=i; int tot=0; fo(i,1,m) { int fx=get(a[i].x),fy=get(a[i].y); if (fx!=fy) { f[fx]=fy; tot++; ans+=a[i].z; } } if (n-1!=tot)printf("-1"); else printf("%lld\n",ans); return 0; }