博客

例6.7.2 还是畅通工程

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

输入格式:

测试数据有多组。每组测试数据的第一行输入村庄数目N ( N<100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离（<1000）。简单起见，村庄从1到N编号。当输入N为0时，表示输入结束。

输出格式:

对于每组测试，在一行上输出最小的公路总长度。

输入样例:


3

1 2 1

1 3 2

2 3 4

0


输出样例:


3


出处:

HDOJ 1233，浙大计算机研究生复试上机考试-2006年

代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

解题代码

#include<bits/stdc++.h>
using namespace std;
int n;
int Map[105][105];
void prim(int t)
{
	int adjvex[n+1];
	bool visited[n+1];
	int dist[n+1];
	for(int i=1;i<=n;i++){
		dist[i]=Map[t][i];
		visited[i]=false;
		if(Map[t][i]<INT_MAX){
			adjvex[i]=t;
		}else{
			adjvex[i]=-1;
		}
	}
	visited[t]=true;
	dist[t]=0;
	for(int i=1;i<n;i++){
		int k,minDist=INT_MAX;
		for(int j=1;j<=n;j++){
			if(dist[j]<minDist&&!visited[j]){
				k=j;
				minDist=dist[j];
			}
		}
		visited[k]=true;
		for(int j=1;j<=n;j++){
			if(dist[j]>Map[k][j]&&!visited[j]){
				dist[j]=Map[k][j];
				adjvex[j]=k;
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=sum+dist[i];
	}
	cout<<sum<<endl;
}

void initMap()
{
	for(int i=0;i<55;i++){
		for(int j=0;j<55;j++){
			Map[i][j]=INT_MAX;
		}
	}
}

int main()
{
	int m,u,v,w;
	while(cin>>n)
	{
		initMap();
		if(n==0) return 0;
		m=(n*(n-1))/2;
		while(m--){
			cin>>u>>v>>w;
			Map[u][v]=w;
			Map[v][u]=w;
		}
		prim(1);
	}
}

解题思路

这题还是使用的Prim算法实现，跟我之前写的那题最小生成树的代码几乎一模一样，在那道题里我写了很清楚的解题思路，大家可以看看那个，链接

：

https://blog.csdn.net/weixin_44546342/article/details/124926750?spm=1001.2014.3001.5501


具体我也就不多说啥了。