从n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总体来说最短

来源：百度知道 编辑：UC知道 时间：2024/05/30 01:47:55
可以将问题抽象为有n个接点，在这n个接点之间建立一个无向图，边上的权值w(i,j)表示村庄i到j之间道路的长度， 在无向图中n个顶点之间，最多可能设置n(n-1)/2条线路，如何在这些线路中选择n-1条线路，以使总的线路最短？对于n个顶点的连通网可以建立许多不同的无向图，每一个无向图都可以表示一个道路网，其中要选择一个最优图，使图上各边之和最小。

要用C语言写 还有就是 村庄到这所医院的距离总体来说最短而不是离最远的村庄最短 ！！

就是个最小生成树问题
#define N 110
int dist[N],g[N][N];
int prim(int n,int cost[][N]){
int ret=0,inf=10000000;
int v[N],i,j,k;
for (i=1;i<=n;i++)
dist[i]=inf,v[i]=0;
for (dist[j=1]=0;j<=n;j++){
for (k=-1,i=1;i<=n;i++)
if (!v[i]&&(k==-1||dist[i]<dist[k]))
k=i;
for (v[k]=1,ret+=dist[k],i=1;i<=n;i++)
if (!v[i]&&cost[k][i]<dist[i])
dist[i]=cost[k][i];
}
return ret;
}
int main()
{
int n,i,j;
puts("输入顶点数：");
scanf("%d",&n);
puts("输入权值邻接矩阵：");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&g[i][j]);
printf("%d\n",prim(n,g));
}