@[To_2051](/user/740254)
```
#include<bits/stdc++.h>
using namespace std;
int ans,n,m,cnt;
struct node{
int u,v,w;
}a[200001];
int fa[100001];
bool cmp(node a,node b)
{
return a.w<b.w;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
bool work()
{
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int eu=find(a[i].u),ev=find(a[i].v);
if(eu==ev) continue;
cnt++;
ans+=a[i].w;
fa[eu]=ev;
}
if (cnt < n - 1)
{
puts ("orz");
return 0;
}
return 1;
}
int main()
{
int pos;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
pos++;
cin>>a[i].u>>a[i].v>>a[i].w;
}
sort(a+1,a+m+1,cmp);
if(work()) cout<<ans;
return 0;
}
```
1.无解判错
2.数组开小
by lalaouye @ 2024-03-24 17:57:05
@[To_2051](/user/740254)
A了：
```cpp
#include<bits/stdc++.h>
using namespace std;
int ans,n,m,cnt;
struct node{
int u,v,w;
}a[200001];
int fa[200001];
bool cmp(node a,node b)
{
return a.w<b.w;
}
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
bool work()
{
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++)
{
int eu=find(a[i].u),ev=find(a[i].v);
if(eu==ev) continue;
cnt++;ans+=a[i].w;
fa[eu]=ev;
if(cnt==n - 1)
{
return 1;
}
}
cout << "orz" <<'\n';
return 0;
}
int main()
{
int pos = 0;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
pos++;
cin>>a[pos].u>>a[pos].v>>a[pos].w;
}
sort(a+1,a+pos+1,cmp);
if(work()) cout<<ans<< endl;
return 0;
}
```
首先，数组开小了。
其次，cnt判断条件是==n - 1 而不是==n，因为树是n个点n - 1条边的连通图，所以边数达到n - 1时就连通了。
最后，函数返回值写反了，cnt==n-1是连通所以返回1，否则不连通输出orz返回0
麻烦关注
by shin_chan_jiang @ 2024-03-24 17:59:42
@[lalaouye](/user/431289) 已关,%%%
by To_2051 @ 2024-03-24 17:59:52
@[shin_chan_jiang](/user/750292) orz
by To_2051 @ 2024-03-24 18:00:46