lqhsr @ 2021-09-17 00:05:35
#include<bits/stdc++.h>
using namespace std;
struct tree{
int to,next,w;
}ed[200005],Ed[200005];
int m,ji,n,head[200005],ans,fa[200005];
bool cmp(tree a,tree b){
return a.w<b.w;
}
int find(int k){
while(k!=fa[k])k=fa[k]=fa[fa[k]];
return k;
}
void kruskal(){
sort(ed+1,ed+m+1,cmp);
for(int i=1;i<=m;i++){
int x=find(ed[i].next),y=find(ed[i].to);
if(x==y)continue;
if(x>y){
fa[y]=x;
}
else
fa[x]=y;
ans+=ed[i].w;
if(++ji==n-1)return ;
}
}
bool tong[200005];
void dfs(int now){
tong[now]=1;
for(int i=head[now];i;i=Ed[i].next){
if(!tong[Ed[i].to])dfs(Ed[i].to);
}
}
void add(int p,int q,int quan){
Ed[++ji].w=quan;
Ed[ji].to=q;
Ed[ji].next=head[p];
head[p]=ji;
}
int main(){
cin>>n>>m;
int cn,cm,cw;
for(int i=1;i<=m;i++){
cin>>cn>>cm>>cw;
ed[i].next=cn,ed[i].to=cm,ed[i].w=cw;
add(cn,cm,cw);
add(cm,cn,cw);
}
dfs(1);
ji=0;
memset(head,0,sizeof(head));
for(int i=1;i<=n;i++)if(!tong[i]){cout<<"orz";return 0;}
for(int i=1;i<=n;i++)fa[i]=i;
kruskal();
cout<<ans;
}
by lqhsr @ 2021-09-17 00:06:48
去掉add函数就AC了
by smyslenny @ 2021-09-17 07:19:26
Ed 应该要开两倍吧。你这加的是双向边。
by smyslenny @ 2021-09-17 07:28:38
实测可过。
by lqhsr @ 2021-09-17 20:56:19
@smyslenny
这。。。我去。。。
我debug了两小时