35
Hint
Hint
Huge input, scanf is recommended.
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#define N 11001using namespace std;int par[N],Rank[N];int n,E;struct edge {int u,v,cost;};edge es[N];void init() {for(int i=0; i<=n; i++) {par[i]=i;Rank[i]=0;}}bool cmp(edge e1,edge e2) {return e1.cost<e2.cost;}int Find(int x) {if(par[x]==x)return x;return par[x]=Find(par[x]);}void unite(int x,int y) {x=Find(x);y=Find(y);if(x==y)return;if(Rank[x]<Rank[y])par[x]=y;else {par[y]=x;if(Rank[x]==Rank[y])Rank[x]++;}}bool same(int x,int y) {return Find(x)==Find(y);}int Kruskal() {int ans=0;for(int i=0; i<E; i++) {edge e=es[i];if(!same(e.u,e.v)) {ans+=e.cost;unite(e.u,e.v);}}return ans;}int main() {while(cin>>n&&n) {E=n*(n-1)/2;for(int i=0; i<E; i++) {scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);}sort(es,es+E,cmp);init();int ans=Kruskal();cout<<ans<<endl;}return 0;}
，当你能梦的时候就不要放弃梦
