最后一个点WA

P3366 【模板】最小生成树

无奈之白 @ 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


|