{
int min[MAXN],ret=0;
int v[MAXN],i,j,k;
for (i=0;i
min[i]=inf,v[i]=0;
for (min[j=0]=0;j
{
for (k=-1,i=0;i
if (!v[i]&&(k==-1||min[i]
k=i;
for (v[k]=1,ret+=min[k],i=0;i
}
cout<
}
return 0;
}
（注：素材和资料部分来自网络，供参考。请预览后才下载，期待你的好评与关注！）
浙江大学计算机专业课考研复试上机真题三来源：考试点
第5题：畅通工程 (8分) [prim算法，最小生成树]
题目要求：某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通(但不一定有直接的公路相连，只要能间接通过公路可达即可)，并要求铺设计算机考研复试
输入样例：
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
输出样例：
3
5
#include
using namespace std;
#define MAXN 110
#define inf 1000000000
int prim(int n,int mat[][MAXN])
if (!v[i]&&mat[k][i]
min[i]=mat[k][i];
}
return ret;
}
int main()
{
int n,d[MAXN][MAXN],a,b,c;
while(cin>>n&&n)
{
for(int i=n*(n-1)/2;i;--i)
{
cin>>a>>b>>c;
d[a-1][b-1]=d[b-1][a-1]=c;
输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 );随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。
输出格式：对每个测试用例，在1行里输出最小的公路总长度。