问题 最小生成树 Memory Limit Exceeded N<=10000,M<=50000
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;# define N 10010int father[N];struct tu{int u,v,cost;}d[N*(N+1)/2];int comp(struct tu x,struct tu y){return x.cost<y.cost;}int Find(int x){if(father[x]==-1)return x;return father[x]=Find(father[x]);}bool jihe(int x,int y){x=Find(x);y=Find(y);if(x==y)return false ;if(x>y)father[x]=y;if(x<y)father[y]=x;return true;}int main(){int i,v,w,edge,n,m;for(;cin>>n>>m;){for(i=0;i<m;i++){ scanf("%d%d%d",&d[i].u,&d[i].v,&d[i].cost);}sort(d,d+m,comp);memset(father,-1,sizeof(father));int sum=0;int count=0;for(i=0;i<n*(n+1)/2;i++){ if(jihe(d[i].u,d[i].v)){ sum+=d[i].cost; ++count; } if(count==n-1)break;}if(count==n-1)cout<<sum<<endl;else cout<<"-1"<<endl;}return 0;}