HDU1102 - Constructing Roads

这里我用的Krustral算法，先把连接的村庄处理，在处理其他未连接村庄

#include<iostream>
#include<cstdio>
#include<cstring>
#include<functional>
#include<algorithm>
using namespace std;
struct node
{
	int from,to;
	int cost;
}e[100*100+10];
int fa[105];
int n,num,sum,k;

int cmp(struct node a,struct node b){return a.cost<b.cost;}
void init()
{
	k=1; sum=0;
	for(int i=1;i<=n;i++)
		fa[i]=i;
}
int getfa(int x)
{
	if(x==fa[x])
		return x;
	else
		return fa[x]=getfa(fa[x]);
}

int merge(int u,int v)
{
	int t1,t2;
	t1=getfa(u);
	t2=getfa(v);
	if(t1!=t2)
	{
		fa[t1]=t2;
		return 1;
	}
	return 0;
}

int main()
{
	int i,j,a,b,t;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
		{
			scanf("%d",&t);
			if(j<i)
				continue;
			e[k].from=i;
			e[k].to=j;
			e[k].cost=t;
			k++;
		}
		scanf("%d",&num);
		for(i=1;i<=num;i++)
		{
			scanf("%d%d",&a,&b);
			merge(a,b);
		}
		k--;
		sort(e+1,e+k+1,cmp);
		for(i=1;i<=k;i++)
		{
			if(merge(e[i].from,e[i].to))
				sum+=e[i].cost;
		}
		printf("%d\n",sum);
	}
	return 0;
}