Prim 84pts WA on #13 求助

P3366 【模板】最小生成树

YONIC @ 2022-04-29 22:01:05

#include<bits/stdc++.h>
#define INF 2147483647
#define M2 (int)(5e3+3)
#define M5 ((int)(1e5+3)<<1)
using namespace std;
int n,m,ans,tot,tot2,now=1,head[M2<<1],vis[M2<<1],dis[M2<<1];
struct{int nxt,to,w;}h[M5<<1];
void add(int u,int v,int w){
    h[++tot].to=v;
    h[tot].nxt=head[u];
    h[tot].w=w;
    head[u]=tot;
}
int prim(){
    for(int i=2;i<=n;++i) dis[i]=INF;
    for(int i=head[1];i;i=h[i].nxt) dis[h[i].to]=min(dis[h[i].to],h[i].w);
    while(++tot2<n){
        int minn=INF;
        vis[now]=1;
        for(int i=1;i<=n;++i){
            if(!vis[i]&&minn>dis[i]){
                minn=dis[i];
                now=i;
            }
        }
        ans+=minn;
        for(int i=head[now];i;i=h[i].nxt){
            int v=h[i].to;
            if(dis[v]>h[i].w&&!vis[v]) dis[v]=h[i].w;
        }
    }
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    while(m--){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    printf("%d",prim());
    return 0;
}

by Southern_Dynasty @ 2022-04-29 22:31:24

@YONIC 您特判图不连通的情况了吗


by Joseph__Joestar @ 2022-05-30 16:04:42

@暗夜黑黑黑手 数据没有图不连通的情况


by kyrie_lrving1992 @ 2022-06-07 16:43:23

你没判断orz


|