poj1251

这道题的题意太明显了，求最小生成树。先面关于图的数字说明，这个图最适合用kruscal来求最小生成树。

poj 1251 Jungle Roads 代码：

#include<iostream>
#include<fstream>
#include<algorithm>
#include<string.h>
using namespace std;

int parent[26];
int n;//vertex num
int edge_num;
struct Edge
{
	int v1;
	int v2;
	int weight;
}edges[100];
int cmp(const void *edge1,const void *edge2)
{
	Edge *e1=(Edge *)edge1;
	Edge *e2=(Edge *)edge2;
	return e1->weight-e2->weight;
}
int find(int v)
{
	while(parent[v]>=0)
		v=parent[v];
	return v;
}
void Union(int r1,int r2)   
{
	if(parent[r1]<=parent[r2])
	{
		parent[r1]+=parent[r2];
		parent[r2]=r1;
	}
	else
	{
		parent[r2]+=parent[r1];
		parent[r1]=r2;
	}
}

int main()
{
	freopen("input.txt","r",stdin);
	while(scanf("%d\n",&n)!=EOF&&n!=0)
	{
		edge_num=0;
		memset(parent,-1,sizeof(int)*n);
		char ch;
		int v1,v2;
		int k;
		for(int t=0;t<n-1;t++)
		{
			scanf("%c %d",&ch,&k);
			v1=ch-'A';
			for(int i=0;i<k;i++)
			{
				int w;
				scanf(" %c %d",&ch,&w);
				edges[edge_num].v1=v1;
				edges[edge_num].v2=ch-'A';
				edges[edge_num++].weight=w;
			}
			scanf("\n");
		}
		qsort(edges,edge_num,sizeof(Edge),cmp);
		int output=0;
		int count=0;
		for(int i=0;i<edge_num;i++)
		{
			if(count==n-1) //successed
				break;
			int r1=find(edges[i].v1);
			int r2=find(edges[i].v2);
			if(r1==r2)
				continue;
			Union(r1,r2);
			output+=edges[i].weight;
			count++;

		}
		/*for(int i=0;i<edge_num;i++)
		{
			cout<<edges[i].v1<<" "<<edges[i].v2<<" "<<edges[i].weight<<endl;
		}*/
	        printf("%d\n",output);
	}
	return 0;
}