Eddy1341 @ 2024-08-19 21:14:21
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int cnt,fa[5005];
long long ans;
struct edge{
int st,to;
long long p;
}E[200005];
int findfa(int x){
if(x==fa[x])return x;
return fa[x]=findfa(fa[x]);
}
bool cmp(edge a,edge b){
return a.p<b.p;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&E[i].st,&E[i].to,&E[i].p);
}
sort(E+1,E+1+m,cmp);
for(int i=1;i<=m;i++){
int x=findfa(E[i].st),y=findfa(E[i].to);
if(x==y)continue;
ans+=E[i].p;
fa[x]=y;
if(++cnt==n-1)break;
}
printf("%lld",ans);
return 0;
}
不想另外跑深搜qwq
by Eddy1341 @ 2024-08-19 21:15:33
最大的问题是,加了#13后,一堆不判orz的题解都过不了
by c20220526 @ 2024-08-19 21:17:57
循环完后cnt没到n-1就是不连通
by yyy_xiaohao @ 2024-08-19 21:18:51
刚想让你判一下每个节点的 root,然后发现你有 cnt。。。。。。
直接看 cnt 是不是