prim ：
```
#include<bits/stdc++.h>
using namespace std;
int n,m;
int u[200001],v[200001],w[200001];
int dis[200001],book[200001];
int h[200001],pos[200001];
int first[200001],next[200001];
int size,inf=0x7fffffff,count1,sum;
void down(int i)
{
int t,flag=0;
while(i*2<=size && flag==0)
{
if(dis[h[i]]>dis[h[i*2]])
t=i*2;
else
t=i;
if(i*2+1<=size)
{
if(dis[h[t]]>dis[h[i*2+1]])
t=i*2+1;
}
if(t!=i)
{
swap(h[t],h[i]);
swap(pos[h[t]],pos[h[i]]);
i=t;
}
else
flag=1;
}
}
void up(int i)
{
if(i==1) return;
int flag=0;
while(i!=1 && flag==0)
{
if(dis[h[i]]<dis[h[i/2]])
{
swap(h[i/2],h[i]);
swap(pos[h[i/2]],pos[h[i]]);
}
else
flag=1;
i/=2;
}
}
int pop()
{
int t;
t=h[1];
pos[h[1]]=0;
h[1]=h[size];
pos[h[1]]=1;
size--;
down(1);
return t;
}
int main()
{
int i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++)
{
first[i]=-1;
dis[i]=inf;
}
for(i=1;i<=m;i++)
cin>>u[i]>>v[i]>>w[i];
for(i=m+1;i<=2*m;i++)
{
u[i]=v[i-m];
v[i]=u[i-m];
w[i]=w[i-m];
}
for(i=1;i<=2*m;i++)
{
next[i]=first[u[i]];
first[u[i]]=i;
}
book[1]=1;
count1++;
dis[1]=0;
k=first[1];
while(k!=-1)
{
dis[v[k]]=w[k];
k=next[k];
}
size=n;
for(i=1;i<=size;i++)
{
h[i]=i;
pos[i]=i;
}
for(i=size/2;i>=1;i--) down(i);
pop();
while(count1<n)
{
j=pop();
book[j]=1;count1++;sum+=dis[j];
k=first[j];
while(k!=-1)
{
if(book[v[k]]==0 && dis[v[k]]>w[k])
{
dis[v[k]]=w[k];
up(pos[v[k]]);
}
k=next[k];
}
}
if(sum>=inf || sum<=0)
cout<<"orz";
else
cout<<sum;
return 0;
}
```
by 泰山飞狐 @ 2019-11-07 16:47:14
~~艹，你这写的什么东西啊~~
by Pisces @ 2019-11-07 16:47:31
@[Pisces](/user/48057)
第一篇是Kruskal
第二篇是Prim
(第一篇的prim请忽略)
by 泰山飞狐 @ 2019-11-07 16:50:01
希更展？使md
by Yike_linen @ 2019-11-07 16:59:38
@[余杭哲](/user/141945) 读完全部代码再说
by 泰山飞狐 @ 2019-11-07 17:05:17
@[Pisces](/user/48057) 这是个手打堆大佬……
by Seauy @ 2019-11-07 17:08:10
@[QuantumCheshireCat](/user/54591) 是不用STL的神仙（纠正）
by Pisces @ 2019-11-07 17:10:49
Hope some masters good at "**shou da dui**" can provide correct answer.
by 泰山飞狐 @ 2019-11-07 17:11:49
只会kruskal的蒟蒻表示懵B
~~开O2？~~
by Yike_linen @ 2019-11-07 17:12:49
@[泰山飞狐](/user/112972) ~~NO~~ STL is uesful, so you should be back on track.
by Seauy @ 2019-11-07 17:15:09