不要加反边
by K0stlin @ 2021-12-18 10:49:43
@[j_steady](/user/559503)
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,len,cnt,ans,sum,fa[10005];
struct node
{
int x,y,len;
}edge[200005];
bool cmp(node x,node y)
{
return x.len<y.len;
}
int find(int x)
{
if (fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void unionn(int x,int y)
{
int fx=find(x);
int fy=find(y);
if (fx!=fy)
{
cnt++;
fa[fx]=fy;
}
return ;
}
void kruskal()
{
sort(edge+1,edge+1+m,cmp);
for(int i=1; i<=m; i++)
{
int x=find(edge[i].x);
int y=find(edge[i].y);
if (x!=y)
{
unionn(x,y);
ans+=edge[i].len;
if (cnt==n-1)
break;
}
}
return ;
}
signed main()
{
cin >> n >> m;
for(int i=1; i<=n; i++)
fa[i]=i;
for(int i=1; i<=m; i++)
cin >> edge[i].x >> edge[i].y >> edge[i].len;
kruskal();
for(int i=1; i<=n; i++)
if (fa[i]==i)
sum++;
if (sum==1)
cout << ans;
else
cout << "orz";
return 0;
}
```
by kdy20100729 @ 2021-12-18 10:50:24
```cpp
for (int i=1;i<=m;i++){
int a,b,c;
scanf ("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
```
去掉 `add(b,a,c)`。
by 404Not_Found @ 2021-12-18 10:51:08
@[404Not_Found](/user/280473) 为什么加了反边会错qwq
by j_steady @ 2021-12-18 10:54:58
@[Kostlin](/user/114830) 谢谢orz
by j_steady @ 2021-12-18 10:56:41
Kruskal 每条边只要知道两端点的信息。
并且你 sort 只 排序了前 $m$ 条边，但你加了 $2m$ 条，实际上你跑 Kruskal 只跑了一半的边。并且 Kruskal 是用并查集维护双向关系的，
by 404Not_Found @ 2021-12-18 11:01:24
@[j_steady](/user/559503)
by 404Not_Found @ 2021-12-18 11:02:56
Kruskal 要知道的只是边的连通性。
by 404Not_Found @ 2021-12-18 11:03:29
@[404Not_Found](/user/280473) 懂了太强了！orz Thank you
by j_steady @ 2021-12-18 11:10:12