链式前向星错了么

P3366 【模板】最小生成树

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了两小时


|