题意：
求出连接各个村庄最小的公路总长度，把最小公路总长度求出来。
思路：
最小生成树原理，带入数据求得。
代码：
prim:
#include<iostream>
#include<cstring> using namespace std;
#define inf 0x3f3f3f3f int main()
{
int n, i,j,b,c,d,min,a[][],visit[],low[];
while(cin>>n,n)
{
memset(visit,,sizeof(visit));
int temp=n*(n-)/;
while(temp--)
{
cin>>b>>c>>d;
a[b][c]=a[c][b]=d;
}
visit[]=;int pos=; //第一次给low赋值
for(i=;i<=n;++i)
{
if(i!=pos) low[i]=a[pos][i];
}
int result=; //运行m-1次，因为至少需要m-1次才能把所有的城市连通
for(i=;i<n;++i)
{
min=inf;
for(j=;j<=n;++j)
{
if(!visit[j]&&min>low[j])
{
min=low[j];
pos=j;
}
}
result+=min;
visit[pos]=;
for(j=;j<=n;++j)
{
if(!visit[j]&&low[j]>a[pos][j])
{
low[j]=a[pos][j];
}
}
}
cout<<result<<endl;
}
return ;
}
krusual:
#include<iostream>
#include<cstdio>
#include<algorithm> using namespace std; struct node
{
int u,v,w;
}; node arr[];
int per[],n; bool cmp(node a,node b)
{
return a.w<b.w;
} void init()
{
for(int i=;i<=n;++i)
{
per[i]=i;
}
} int find(int x)
{
if(x==per[x]) return x;
return per[x]=find(per[x]);
} bool join(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
{
per[fx]=fy;
return ;
}
return ;
} int main()
{
int m;
while(cin>>n,n)
{
init();
m=n*(n-)/;
for(int i=;i<m;++i)
{
cin>>arr[i].u>>arr[i].v>>arr[i].w;
}
sort(arr,arr+m,cmp);
int sum=;
for(int i=;i<m;++i)
{
if(join(arr[i].u,arr[i].v))
{
sum+=arr[i].w;
}
}
cout<<sum<<endl;
}
return ;
}