kruscal 并查集.txt

ACM资料大集合

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
using namespace std;

//kruscal 并查集
/*
输入：
6 10
1 2 6
1 3 1
1 4 5
3 2 5
3 4 5
5 2 3
5 3 6
6 5 6
6 3 4
6 4 2

输出：
15
*/
#define NMAX 100
typedef struct node
{
	int fa;
	int rank;
}node;

typedef struct arc
{
	int nd1;
	int nd2;
	int cost;
}arc;

node point[NMAX];
arc shuru[NMAX];

bool cmp(arc a,arc b)
{
	return a.cost<b.cost;
}

void init(int pnum)
{
	int i;
	for(i=0;i<NMAX;i++)
	{
		point[i].fa=-1;
		point[i].rank=1;
	}
	sort(shuru+1,shuru+1+pnum,cmp);
}

int find(int x)
{
	int root=x,tt;
	while(point[root].fa!=-1) root=point[root].fa;
	while(point[x].fa!=-1)
	{
		tt=point[x].fa;
		point[x].fa=root;
		x=tt;
	}
	return root;
}

bool join(int a,int b)
{
	a=find(a);
	b=find(b);
	if(a!=b)
	{
		if(point[a].rank>point[b].rank) 
		{
			point[b].fa=a;
			point[a].rank+=point[b].rank;
		}
		else
		{
			point[a].fa=b;
			point[b].rank+=point[a].rank;
		}
		return true;
	}
	return false;
}

int solve(int pnum)
{
	int i,ans=0,pa,pb;
	init(pnum);
	for(i=1;i<=pnum;i++)
	{
		if(join(shuru[i].nd1,shuru[i].nd2)==true)
			ans+=shuru[i].cost;
	}
	return ans;
}
int main()
{
	int i,pnum,nnum;
	scanf("%d %d",&nnum,&pnum);
	for(i=1;i<=pnum;i++)
	{
		scanf("%d %d %d",&shuru[i].nd1,&shuru[i].nd2,&shuru[i].cost);
	}
	printf("%d\n",solve(pnum));
	return 0;
}