还是畅通工程

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

INPUT

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。
当N为0时，输入结束，该用例不被处理。

OUTPUT

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

Sample Output

3
5

一道典型的最小生成树的水题，没什么难度，直接看代码吧。

克鲁斯卡尔版本

#include<bits/stdc++.h>
using namespace std;
int n,res,f[110],cnt;
struct node    //每一条边
{
	int st,end,w;  //起点，终点，权值
};
bool operator<(const node &s1,const node &s2)   //优先队列的自定义顺序
{
	return s1.w>s2.w;
}
priority_queue<node> pq;   //优先队列
void init()  //数据初始化
{
	res=0,cnt=0;
	while(!pq.empty())	pq.pop();
	for(int i=0;i<=n;i++)	f[i]=i;
}
int find_root(int x)    //找根节点，用于判断是否已经连通
{
	return x==f[x]?x:f[x]=find_root(f[x]);
}
void union_set(int a,int b)   //连接这两个点
{
	f[find_root(a)]=find_root(b);
}
int main()
{
	while(cin>>n,n)
	{
		init();
		node a;
		for(int i=0;i<n*(n-1)/2;i++)
		{
			cin>>a.st>>a.end>>a.w;
			pq.push(a);
		}
		while(!pq.empty()&&cnt<n)
		{
			int fa=find_root(pq.top().st);
			int fb=find_root(pq.top().end);
			if(fa!=fb)//这个两个点没有连通 
			{
				res+=pq.top().w;//答案加上这条路径 
				union_set(pq.top().st,pq.top().end);
			}
			pq.pop();
		}
		cout<<res<<endl;
	}
	return 0;
}

普利姆版本

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=110;
int n,g[N][N],low[N],vis[N],res;
void prim()
{
	vis[1]=1;
	for(int i=1;i<=n;i++)	low[i]=g[i][1];
	for(int C=1;C<n;C++)
	{
		int id=-1;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i]&&(id==-1||low[i]<low[id]))	id=i;
		}
		res+=low[id];
		vis[id]=1;
		for(int i=1;i<=n;i++)
		{
			if(!vis[i]&&low[i]>g[i][id])	low[i]=g[i][id];
		}
	}
}
int main()
{
	while(cin>>n,n)
	{
		for(int i=1;i<=n;i++)	for(int j=1;j<=n;j++)	g[i][j]=(i==j?0:inf);
		memset(vis,0,sizeof(vis));
		memset(low,inf,sizeof(low));
		res=0;
		int m=n*(n-1)/2;
		while(m--)
		{
			int a,b,w;
			scanf("%d %d %d",&a,&b,&w);
			g[a][b]=min(g[a][b],w);
			g[b][a]=min(g[b][a],w);
		}
		prim();
		cout<<res<<endl;
	}
	return 0;
}