三个点RE求解

P3366 【模板】最小生成树

detor @ 2022-07-15 15:00:29

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
long long n,m,sum,hs;
int book[100010];
int tot,h[100010],v[200010],w[200010],ne[200010];
struct pir{
    int x,y;
}hp[200010];

void add(int a,int b,int c){
    v[tot]=b;w[tot]=c;ne[tot]=h[a];
    h[a]=tot++;
    return;
}
void siftdown(int i)
{
    if(i==0)return;
    int t=i;
    while(2*i<=hs)
    {
        if(hp[2*i].x<hp[t].x)
            t=2*i;
        if(2*i+1<=hs&&hp[2*i+1].x<hp[t].x)
            t=2*i+1;
        if(i!=t)
            swap(hp[i],hp[t]);
        else
            return;
        i=t;
    }
    return ;
}

void siftup(int i)
{
    while(i>1)
    {
        if(hp[i].x<hp[i/2].x)
            swap(hp[i],hp[i/2]);
        else
            return;
        i/=2;
    }

    return;
}
int main()
{
//  freopen("kruskal.in","r",stdin);
    int a,b,c;
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }

    sum=0;
    hp[1].x=0;
    hp[1].y=1;
    hs++;
    while(hs)
    {

        pir t=hp[1];
        hp[1]=hp[hs--];
        siftdown(1);
        a=t.y;
        if(book[a]) 
            continue;
        book[a]=1;
        sum+=t.x;
        for(int i=h[a];~i;i=ne[i]){
            hs++;
            hp[hs].x=w[i],hp[hs].y=v[i];
            siftup(hs);
        }

    }

    for(int i=1;i<=n;i++){
        if(book[i]==0){
            cout<<"orz";
            return 0;
        }
    }
    cout<<sum<<endl;

    fclose(stdin);
    return 0;
}

by Zvelig1205 @ 2022-07-15 15:10:12

手打堆?%%%


by detor @ 2022-07-15 17:21:34

@极冬寒雪 我这种用Devc++的菜鸡STL调试不了


by Zvelig1205 @ 2022-07-15 17:54:12

@detr devc++能调试STL,不加查看就行白,我也用的dev


|