你的并查集、、
by 谬悠 @ 2019-11-21 16:10:25
这题不用那么麻烦吧,直接路径压缩就行了,而且成功选完n-1条边就一定联通
by 谬悠 @ 2019-11-21 16:11:30
这题不用队列。
by 谬悠 @ 2019-11-21 16:12:07
直接sort就行了
by 谬悠 @ 2019-11-21 16:12:17
为什么你的码量那么大
by 谬悠 @ 2019-11-21 16:12:57
```cpp
const int maxn=210005;
struct orz{
int x,y,z;
}a[maxn];
int n,m,prt[maxn],ans=0,bj;
bool cmp(orz x,orz y){
return x.z<y.z;
}
int find(int x){
if(prt[x]==x)return x;
prt[x]=find(prt[x]);
return prt[x];
}
void kruskal(){
int f1,f2,k,i;
k=0;
for(i=1;i<=n;i++)prt[i]=i;
for(i=1;i<=m;i++){
f1=find(a[i].x);
f2=find(a[i].y);
if(f1!=f2){
ans+=a[i].z;
prt[f1]=f2;
k++;
if(k==n-1)break;
}
}
if(k<n-1){
cout<<"orz"<<endl;
bj=0;
return;
}
}
int main(){
cin>>n>>m;
ans=0;bj=1;
for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+m+1,cmp);
kruskal();
if(bj)cout<<ans<<endl;
return 0;
}
```
by 谬悠 @ 2019-11-21 16:13:34
、、、早期版本、、、比较长
by 谬悠 @ 2019-11-21 16:14:07
@[谬悠](/user/234271) 大佬,我还是想知道为什么我崩了,我去掉后面的判断连通还是只过1,3,其他的都wa
by nightmare004 @ 2019-11-21 16:47:00
@[nightmare004](/user/103646) QAQ,窝是菜,另外泥这个复杂度可能。。。。
by 谬悠 @ 2019-11-21 16:48:52
@[nightmare004](/user/103646) 如果不想放弃的话估摸着是合并写错了?
by 谬悠 @ 2019-11-21 16:49:42