2 u011134403 u011134403 于 2013.06.24 14:46 提问

最小生成树问题,c代码
111

题目描述
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.

输入
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 500). The following lines contain the N x N conectivity matrix, where each element shows the distance from one farm to another. Logically, they are N lines of N space-separated integers. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem

输出
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
样例输入
6
0 6 1 5 100 100
6 0 5 100 3 100
1 5 0 5 6 4
5 100 5 0 100 2
100 3 6 100 0 6
100 100 4 2 6 0

样例输出
15

提示

题意简述:在n个城市之间铺设光缆,铺设光缆费用很高且各个城市之间铺设光缆的费用不同。设计目标是使这n个城市之间的任意2个城市都可以直接或间接通信,并且要使铺设光缆的费用最低。

解题思路:这样的问题是一个求最小生成树的问题。解决这个问题的方法就是在由n个城市结点和n(n-1)/2条费用不同的边构成的无向连通图中找出最小生成树。首选Prim算法,也可以用Kruskal算法。

样例的数据来源于教材图7.16,用邻接矩阵表示。

生词:

optical fiber   光缆

N x N conectivity matrix N x N的邻接矩阵

space-separated integers  空格隔开的整数

the diagonal 对角线

1个回答

u014296677
u014296677   2014.06.13 10:45

#include

#define Max 200000
#define N 1100
int a[N][N],low[N],visited[N];
int n;

int prim()

{
int i,j,t,Min,sum=0;
visited[1]=1;t=1;
for(i=1;i<=n;i++)
if(i!=t) low[i]=a[t][i];
for(i=1;i {
Min=Max;
for(j=1;j if(visited[j]==0&&Min>low[j])
{
Min=low[j];t=j;
}
sum+=Min;
visited[t]=1;
for(j=1;j<=n;j++)
if(visited[j]==0&&low[j]>a[t][j])
low[j]=a[t][j];
}
return sum;
}

int main()
{
int i,j,k;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
k=prim();
printf("%d\n",k);
}
return 0;
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
最小生成树问题中Kruskal算法和Prim算法的C语言实现
最小生成树问题中 Kruskal算法 和 Prim算法 的C语言实现
贪心法--最小生成树的Prim算法和Kruskal算法
贪心法的实现过程和思想
Prim算法最小生成树c++实现
Prim算法最小生成树c++实现标签(空格分隔): Prim 算法 c++最近离散课上讲到了Prim算法实现最小生成树,现在用c++来实现。本文代码来源于乔帮主伪代码。简述对于给定的带权图G,为了使得生成树T的权w(T)最小,我们可以使用贪心算法。求最小生成树的贪心法:1.选择一个初始点v1v_1; 2.为了使得生成树的权极小化,选择v1v_1的最小权邻点,并将其连接到v1v_1; 3.选择{v
贪心法——C语言实现最小代价生成树
【最小代价生成树】 无向连通图G:含n个顶点 若G存在由n-1条边连通n个顶点的子图G',则称G'为G的一棵生成树。 若G的每一条边都赋了一个权值,则称此图为网络。 最小代价生成树:在一个网络的各种生成树中,具有最小代价的生成树。 【普里姆算法】 设网络G={ V,E },V={ 0,1,2,3,…,n-1 },设U为V的子集(初始U为空集); 然后从集合V-U中找出一个顶点x;
经典算法6:贪心算法之最小生成树
1、问题描述      设G =(V,E)是无向连通带权图,即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树。      网络的最小生成树在实际中有广泛应用。例如,在设计通信网络时,用图的顶点表示城市,用边(v,w)的权c
最小生成树+设计文档
数据结构的最小生成树问题 数据结构的最小生成树问题 数据结构的最小生成树问题
最小生成树(贪心算法)
最小生成树问题——连接n个针脚,可以使用n-1根连线,每个连线连接两个针脚,使得所使用的连线长度最短     抽象为图问题,一个连通无向图G = (V, E),V是针脚的集合,E是针脚之间的可能连接,且对于每条边都有权重w(u, v),希望找到一个无环子集,T属于E,权重之和最小 通用方法——在每个时刻生长最小生成树的一条边,并在整个策略的实施过程中,管理一个遵守下述循环不变式的边集合
贪心法之最小生成树之Kruskal算法
A,实际应用:现实生活中经常需要计算某种方案的最小成本问题,比如希望利用最少量的电缆线连接一座建筑物中所有的计算机;再比如希望以最小的成本连接一个网络中的所有路由器等问题。把整个问题抽象成一个无向图,解决问题就是要构建一棵包含图中所有节点的树,并使构造出的树的总权值最小,即求解图的最小生成树问题。下面将介绍用于构造该种树的方法,Kruskal算法。 B,克鲁斯卡尔(Kruskal)算法:假设无向
贪心算法 - 最小生成树 Prim算法
一个无向带权图G=(V,E),其中n个顶点Vertex,以及连接各个顶点之间的边Edge,可能有些顶点之间没有边,每条边上的权值都是非负值。 生成树: G的一个子图,包含了所有的Vertex,和部分的Edge。 最小生成树: 所有的生成树中,各条Edge上的权值总和最小的一个。 例子:设计通信网络时,各个城市之间铺设线路,最经济的方案。 最小生成树性质: G=(V,E), S是V的真
算法java实现--贪心算法--最小生成树问题--Prim算法
最小生成树问题(Dijkstra算法)的java实现(贪心算法) 具体问题描述以及C/C++实现参见网址