学步园

5 29
1 2 674
2 3 249
3 4 672
4 5 933
1 2 788
3 4 147
2 4 504
3 4 38
1 3 65
3 5 6
1 5 865
1 3 590
1 4 682
2 4 227
2 4 636
1 4 312
1 3 143
2 5 158
2 3 516
3 5 102
1 5 605
1 4 99
4 5 224
2 4 198
3 5 894
1 5 845
3 4 7
2 4 14
1 4 185

92

#include <cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100002
#define M 1000002
struct edge
{
	int u;
	int v;
	int len;
};
edge a[M];
int rear;
vector<edge> Q[N];//顶点对应的邻接表
int visited[N];//记录是否已经置于最小生成树集合中

void init(int n)
{
	for(int i=1;i<=n;i++)
		visited[i] = 0;
}

void ins()//向堆添加数据
{
	int i = rear, j = i/2;
	edge temp = a[rear];
	while (j>=1 && temp.len < a[j].len)
	{
		//cout << "test" << endl;
		a[i] = a[j];
		i = j;
		j = j / 2;
	}
	a[i] = temp;
}

void del()//删除堆的根
{
	if (rear < 1)
		return;
	edge temp = a[1] = a[rear];
	rear--;
	int i = 1,j=2*i,lower=i;
	while (j <= rear)
	{
		//cout << "test" << endl;
		lower = j;
		if (j + 1 <= rear && a[j].len > a[j + 1].len)
			lower = j + 1;
		if (temp.len > a[lower].len)
		{
			a[i] = a[lower];
			i = lower;
			j = i*2;
		}
		else
		{
			break;
		}
	}
	a[i] = temp;
}

int prim(int n)
{
	int sum=0;
	vector<edge>::iterator it;
	for(it = Q[1].begin();it!=Q[1].end();it++)
	{
		edge e = *it;
		if(visited[e.v])
			continue;
		rear++;
		a[rear]=e;
		ins();
	}
	visited[1] = 1;
	int count = 1;
	while(1)
	{
		while(visited[a[1].v])
			del();
		//cout<<a[1].v<<endl;
		sum+=a[1].len;
		count++;
		if(count == n)
			break;
		int v = a[1].v;
		visited[v] = 1;
		del();
		vector<edge>::iterator it;
		for(it = Q[v].begin();it!=Q[v].end();it++)
		{
			edge e = *it;
			if(visited[e.v])
				continue;
			rear++;
			a[rear]=e;
			ins();
		}
	}
	return sum;
}

int main()
{
	int m,n,u,v,len;
	if(scanf("%d%d",&n,&m)==2)
	{
		rear=0;
		init(n);
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&len);
			edge temp1;
			temp1.u = u;
			temp1.v = v;
			temp1.len = len;
			edge temp2;
			temp2.u = v;
			temp2.v = u;
			temp2.len = len;
			Q[u].push_back(temp1);
			Q[v].push_back(temp2);
		}
		printf("%d\n",prim(n));
	}
	return 0;
}