代码如下：
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 400010
struct fun
{
int u;
int v;
int Next;
int edge;
}a[N];
int fa[N],First[N];
int n,m,tot=-1;
inline void add(int x,int y,int z)
{
a[++tot].v=y;
a[tot].u=x;
a[tot].Next=First[x];
First[x]=tot;
a[tot].edge=z;
}
bool cmp(fun wjl,fun szy)
{
return wjl.edge<szy.edge;
}
int Find(int x)
{
if(fa[x]==x)return x;
return fa[x]=Find(fa[x]);
}
int kruskal()
{
int ans=0,num=0;
for(int i=1;i<=m;i++)
{
int x=a[i].u,y=a[i].v;
int xx=Find(x),yy=Find(y);
if(xx!=yy)
{
fa[xx]=yy;
ans+=a[i].edge;
num++;
}
if(num==n-1)return ans;
}
if(num!=n-1)return -1;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
sort(a+1,a+1+m,cmp);
int ans=kruskal();
if(ans==-1)printf("orz\n");
else printf("%d\n",ans);
return 0;
}
```
by Alexandra @ 2022-08-22 17:20:17
@[wangzl](/user/222039) 扯淡。
by CmsMartin @ 2022-08-22 17:25:10
@[wangzl](/user/222039) kruskal不是存边吗
by happybob @ 2022-08-22 17:26:56
@[Alexandra](/user/341329) 试了一下，不建双向边有79
by freoepn @ 2022-08-22 17:27:41
将 ```sort``` 的 $m$ 改成 $2m$ , ```kruskal``` 的 $m$ 改成 $2m$ 就过了。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 400010
struct fun
{
int u;
int v;
int Next;
int edge;
}a[N];
int fa[N],First[N];
int n,m,tot=-1;
inline void add(int x,int y,int z)
{
a[++tot].v=y;
a[tot].u=x;
a[tot].Next=First[x];
First[x]=tot;
a[tot].edge=z;
}
bool cmp(fun wjl,fun szy)
{
return wjl.edge<szy.edge;
}
int Find(int x)
{
if(fa[x]==x)return x;
return fa[x]=Find(fa[x]);
}
int kruskal()
{
int ans=0,num=0;
for(int i=1;i<=2*m;i++)
{
int x=a[i].u,y=a[i].v;
int xx=Find(x),yy=Find(y);
if(xx!=yy)
{
fa[xx]=yy;
ans+=a[i].edge;
num++;
}
if(num==n-1)return ans;
}
if(num!=n-1)return -1;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
sort(a+1,a+1+2*m,cmp);
int ans=kruskal();
if(ans==-1)printf("orz\n");
else printf("%d\n",ans);
return 0;
}
```
by Lavaloon @ 2022-08-22 17:28:20
tot起始值改为0，建单向边过了
by freoepn @ 2022-08-22 17:30:17
其实是不需要双向边的，改成单向边，统一 $a$ 从 $1$ 开始即可。
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 400010
struct fun
{
int u;
int v;
int Next;
int edge;
}a[N];
int fa[N],First[N];
int n,m,tot=0;
inline void add(int x,int y,int z)
{
a[++tot].v=y;
a[tot].u=x;
a[tot].Next=First[x];
First[x]=tot;
a[tot].edge=z;
}
bool cmp(fun wjl,fun szy)
{
return wjl.edge<szy.edge;
}
int Find(int x)
{
if(fa[x]==x)return x;
return fa[x]=Find(fa[x]);
}
int kruskal()
{
int ans=0,num=0;
for(int i=1;i<=m;i++)
{
int x=a[i].u,y=a[i].v;
int xx=Find(x),yy=Find(y);
if(xx!=yy)
{
fa[xx]=yy;
ans+=a[i].edge;
num++;
}
if(num==n-1)return ans;
}
if(num!=n-1)return -1;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
sort(a+1,a+1+m,cmp);
int ans=kruskal();
if(ans==-1)printf("orz\n");
else printf("%d\n",ans);
return 0;
}
```
by Lavaloon @ 2022-08-22 17:34:55
@[qujunyi](/user/347471) @[Lavaloon](/user/201858) 谢谢大佬，邻接表出错了，已经过了
by Alexandra @ 2022-08-22 17:34:59