crzcqh @ 2023-08-13 12:36:42
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,w,cnt,ans;
int fa[5005],vis[5005],head[5005];
struct node{
int u,v,w,ne;
}e[200010];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int merge(int x1,int x2){
if(find(x1)!=find(x2)){
fa[x1]=x2;
return 1;
}
return 0;
}
void add(int u,int v,int w){
e[++cnt].v=v;
e[cnt].u=u;
e[cnt].w=w;
e[cnt].ne=head[u];
head[u]=cnt;
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=e[i].ne){
if(vis[e[i].v]==0) dfs(e[i].v);
}
}
bool cmp(node a,node b){
return a.w<b.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dfs(1);
for(int i=1;i<=n;i++)
if(vis[i]==0){
cout<<"orz";
return 0;
}
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
if(merge(e[i].u,e[i].v)){
ans+=e[i].w;
}
}
cout<<ans;
return 0;
}by Polaris_flame @ 2023-08-13 13:00:47
@crzcqh 你的merge函数写错了（还有这道题不用dfs一遍的）,改了一下AC了
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,ans=0,num=0;
int fa[5005],head[5005];
struct node{
int u,v,w;
}e[200010];
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int merge(int x1,int x2){
if(find(x1)!=find(x2)){
fa[find(x1)]=find(x2);
return 1;
}
return 0;
}
bool cmp(node a,node b){
return a.w<b.w;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
for(int i=1;i<=n;i++) fa[i]=i;
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
if(merge(e[i].u,e[i].v)){
//printf("(%d,%d)\n",e[i].u,e[i].v);
num++;
ans+=e[i].w;
}
}
if(num<n-1) printf("orz\n");
else cout<<ans;
return 0;
}by crzcqh @ 2023-08-13 20:13:42
@Polaris_flame 好的，谢谢！
by Soda_mew @ 2023-08-14 18:04:10
克鲁斯卡尔对吧？不需要dfs的其实，另外merge函数写错了，题解里有大佬列出路径压缩为什么这样写，建议去看看