无奈之白 @ 2022-06-18 23:31:31
#include<bits/stdc++.h>
using namespace std;
const int MAX=1e6;
int n,m,tot;
struct edge {
int u,v,w,next;
} e[MAX];
int cmp(edge x,edge y){
return x.w<y.w;
}
int head[MAX],f[MAX];
void add_edge(int u,int v,int w){
e[++tot].u=u,e[tot].v=v,e[tot].w=w;
e[tot].next=head[u],head[u]=tot;
}
int findf(int x){
return x==f[x]?x:f[x]=findf(f[x]);
}
bool merge(int x,int y){
int fx=findf(x),fy=findf(y);
if(fx!=fy){
f[fx]=fy;
return 1;
}
else return 0;
}
int main() {
cin>>n>>m;
int x,y,z;
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
add_edge(x,y,z),add_edge(y,x,z);
}
sort(e+1,e+1+tot,cmp);
int cnt=0,ans=0;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=tot;i++){
x=e[i].u,y=e[i].v;
if(merge(x,y)){
cnt++,ans+=e[i].w;
if(cnt==n-1) break;
}
} if(ans)cout<<ans;
else cout<<"orz";
return 0;
}
by Cardinal_Oath @ 2022-06-18 23:41:22
特判不对吧。
by tatianyi @ 2022-06-22 22:22:44
你的代码没能判断出这图是不连通的图。
虽然不连通,但是算法仍然会计算出各个边的权值和,就不能使用ans来判断是否为联通图。
by Abel_ILmjh @ 2022-07-15 09:53:41
最后的特判应该是cnt<n-1