$1≤M≤2×10^5$
by 子翮 @ 2020-04-22 08:46:40
@[hxl23333](/user/272531)
```cpp
这句话else father[x]=find(x);
else father[x] = find(father[x]);
```
by KellyFrog @ 2020-04-22 08:47:00
数组空间开小了...
by 蒟___ @ 2020-04-22 08:47:37
路径压缩写假了
by 子翮 @ 2020-04-22 08:48:28
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,father[5006],cnt;
int sum;
struct node{
int q,z,w;
}a[200006];
bool cmp(struct node x,struct node y){
if(x.w<y.w) return true;
else return false;
}
int find(int x){
if(x==father[x]) return x;
else father[x]=find(father[x]);
return father[x];
}
void kk(){
int x,y,i;
for(i=0;i<m;i++){
x=find(a[i].q);
y=find(a[i].z);
if(x==y) continue;
father[y]=x;
sum+=a[i].w;
cnt++;
if(cnt==n-1) break;
}
}
int main(){
int i;
cin>>n>>m;
for(i=1;i<=n;i++)
father[i]=i;
for(i=0;i<m;i++)
cin>>a[i].q>>a[i].z>>a[i].w;
sort(a,a+m,cmp);
kk();
cout<<sum;
return 0;
}
```
实测能A
by Toclhu @ 2020-04-22 08:48:55
@[hxl23333](/user/272531)
by Toclhu @ 2020-04-22 08:49:29
```cpp
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,father[5006],cnt;
long long sum;
struct node{
int q,z,w;
};
bool cmp(struct node x,struct node y){
if(x.w<y.w) return true;
else return false;
}
int find(int x){
if(x==father[x]) return x;
else father[x]=find(x);
return father[x];
}
void kk();
struct node a[200006];
int main(){
int i;
cin>>n>>m;
for(i=1;i<=n;i++)
father[i]=i;
for(i=0;i<m;i++)
cin>>a[i].q>>a[i].z>>a[i].w;
sort(a,a+m,cmp);
kk();
cout<<sum;
return 0;
}
void kk(){
int x,y,i;
for(i=0;i<m;i++){
x=find(a[i].q);
y=find(a[i].z);
if(x==y) continue;
father[y]=x;
sum+=a[i].w;
cnt++;
if(cnt==n-1) break;
}
}
```
by 只狼 @ 2020-04-22 08:52:25
开大后还是mle了。。。
by 只狼 @ 2020-04-22 08:52:58
@[hxl23333](/user/272531) 路径压缩错了呀
by Toclhu @ 2020-04-22 08:54:02
你给我的代码里结构体数组放上面能过，放下面却过不了@[Oahgt](/user/316443)
by 只狼 @ 2020-04-22 08:57:31