写 Kruskal 啊。。
又好写又能拓展
by yurzhang @ 2019-06-08 18:44:20
@[无赖学哥](/space/show?uid=174867)
```
#include<algorithm>
#include<iostream>
using namespace std;
const int N=5005,M=200005;
struct edge{
int x,y,z;
}a[M];
int fa[N],cnt,res;
bool cmp(edge a,edge b){
return a.z<b.z;
}
int find(int x){
if(fa[x]!=x)fa[x]=find(fa[x]);
return fa[x];
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<m;i++)cin>>a[i].x>>a[i].y>>a[i].z;
sort(a+1,a+m+1,cmp);
for(int i=1;i<n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int f1=find(a[i].x),f2=find(a[i].y);
if(f1!=f2){
cnt++;
res+=a[i].z;
fa[f1]=f2;
}
}
if(cnt<n-1)cout<<"orz";
else cout<<res;
return 0;
}
```
by fzhfzh @ 2019-06-08 18:49:48
Kruskal算法
by fzhfzh @ 2019-06-08 18:50:14
~~这标题~~
by lukelin @ 2019-06-08 18:53:43
@[yurzhang](/space/show?uid=126486)
写 Link-Cut Tree 啊。。
又好写又能拓展 (
by NaCly_Fish @ 2019-06-08 19:00:40
@[NaCly_Fish](/space/show?uid=115864) Orz神仙爆切橙题
by t162 @ 2019-06-08 19:02:04
@[NaCly_Fish](/space/show?uid=115864) 你这种巨佬请不要随意进入蒟蒻的讨论，会把我们学习OI的所有决心全变成绝望！！！！
by 赤霞QvQ @ 2019-06-08 19:03:01
@[fzhfzh](/space/show?uid=158050) 可惜了，我不会写Kruskal……
by 赤霞QvQ @ 2019-06-08 19:03:32
@[NaCly_Fish](/space/show?uid=115864) 求求巨佬帮主蒟蒻，查查我的Prim哪里写错了………………
by 赤霞QvQ @ 2019-06-08 19:04:27
还是喜欢prim
by 浮梦月夜寂ღ @ 2019-06-08 19:12:20