Kruskal不用考虑重边,但要考虑是否这棵树是MST,即是否包含所有点
#include<cstdio> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct Edge{ int l,r; int val; } edge[20005]; int n,m,x,y,cnt; ll ans; int tree[1005]; bool cmp(const Edge x,const Edge y) { return x.val>y.val; } int find(int x) { return tree[x]==x?x:tree[x]=find(tree[x]); } void Kruskal() { for(int i = 1;i<=n;++i) tree[i] = i; for(int i = 0;i<m;++i) { x = find(edge[i].l); y = find(edge[i].r); if(x!=y) { tree[x] = y; ans += edge[i].val; cnt++; } if(cnt==n-1) break; } printf("%lld\n",ans=(cnt==n-1)?ans:-1);//判断所有点都在里面 } int main() { while(~scanf("%d%d",&n,&m)) { ans = cnt = 0; for(int i = 0;i<m;++i) scanf("%d%d%d",&edge[i].l,&edge[i].r,&edge[i].val); sort(edge,edge+m,cmp); Kruskal(); } return 0; }