有关问题 最小生成树 Memory Limit Exceeded N<=10000,M<=50000
问题 最小生成树 Memory Limit Exceeded N<=10000,M<=50000
------解决方案--------------------
恭喜LZ 前来接分
------解决方案--------------------
恭喜LZ 前来接分
- C/C++ code
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; # define N 10010 int 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; }
------解决方案--------------------
恭喜LZ 前来接分
------解决方案--------------------
恭喜LZ 前来接分