poj 1251第二种解法

kruskal思想：

    对图G的所有边按权值从小到大排序，每次取一条边，若此边的两个结点属于同一个连通分量，则舍弃这条边；若不属于同一个连通分量，则将这条边加入到最小生成树中。当所有结点属于同一个连通分量时，构造完毕。

    kruskal设计：

    一个边的结构体。有几个关键问题：

   如何判断两个结点是否属于一个连通分量：

 每个连通分量都用其中一个结点来标识，p[]数组用来表示结点的父节点（初始p[i]=i），真正的头结点满足p[i]=i；首先根据传进来的边的两个顶点，用findSet找出点所属的父节点（递归，条件x==p[x]），若父节点相同，显然属于同一个连通分量，直接返回，测试下一条边；否则，合并两个连通分量。

   如何合并两个连通分量：

两个连通分量x,y，是将x合并到y还是y合并到x？这就用一个rank数组来确定（初始rank[]=0）。如果rank[x]>rank[y]，则将y合并到x，即p[y] = x；否则，将x合并到y，即p[x] = y，如果rank[x]=rank[y]，还要将rank[y]加1。

 

例：

初始传入最小边ab，rank[a]==0==rank[b]，则将rank[b]加1，p[a]=b；

传入边ac，a属于分量b，c属于分量c，且rank[b]==1 > 0==rank[c]，则p[c]=b；

同理传入ad，ae之后，p[d],p[e]都等于b。

传入边fg，同传入ab；

传入边bg，rank[b]==1==rank[g]，则p[g]=b，rank[b]++；

传入边be，b与e同属于b，直接返回，最小生成树构造完毕！

代码如下：

 

#include <iostream>
using namespace std;
int n;					//结点个数
int m;					//边的条数
int p[26];				//用来寻找某个点属于的子连通图（P[i] == i）
int rank[26];			//若i属于某连通分量且p[i] = i;则用rank[i]来判断合并两个连通分量将哪个作为哪个的子集
int result;

typedef struct edge
{
	int v1;
	int v2;
	int w;
}Edge;
Edge e[75];

int cmp(const void *a, const void *b)
{
	return (*(Edge *)a).w - (*(Edge *)b).w;
}

void initial()
{
	memset(e,0,sizeof(Edge)*75);
	m = 0;
	result = 0;
}

int findSet(int x)			//找属于的集合
{
	if(x != p[x])
		p[x] = findSet(p[x]);
	return p[x];
}

void Union(int x, int y, int w)		/*****更改集合*****/
{
	if(x == y) return;
	if(rank[x] > rank[y])
	{
		p[y] = x;
	}
	else
	{
		p[x] = y;
		if(rank[x] == rank[y])
			rank[y] ++;
	}
	result += w;
}

int kruskal()
{
	int i;
	for(i = 0; i < 26; i++)
	{
		rank[i] = 0;
		p[i] = i;
	}
	qsort(e,m,sizeof(Edge),cmp);
	for(i = 0; i < m; i++)
		Union(findSet(e[i].v1), findSet(e[i].v2), e[i].w);
	return result;
}

int main()
{
	int i,j;
	char v1;
	int num;
	char v2;
	int w;
	while(cin>>n && n!=0)
	{
		initial();
		for(i = 1; i < n; i++)
		{
			cin>>v1>>num;
			for(j = 0; j < num; j++)
			{
				cin>>v2>>w;
				e[m].v1 = v1-'A';
				e[m].v2 = v2 -'A';
				e[m].w = w;
				m++;
			}
		}
		printf("%d\n",kruskal());
	}
	return 0;
}