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