u011134403 于 2013.06.24 14:46 提问

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

optical fiber 　　光缆

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

space-separated integers　　空格隔开的整数

the diagonal　对角线

1个回答

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;
}

Prim算法最小生成树c++实现
Prim算法最小生成树c++实现标签（空格分隔）： Prim 算法 c++最近离散课上讲到了Prim算法实现最小生成树，现在用c++来实现。本文代码来源于乔帮主伪代码。简述对于给定的带权图G，为了使得生成树T的权w(T)最小，我们可以使用贪心算法。求最小生成树的贪心法：1.选择一个初始点v1v_1; 2.为了使得生成树的权极小化，选择v1v_1的最小权邻点，并将其连接到v1v_1； 3.选择{v

【最小代价生成树】 无向连通图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；

1、问题描述      设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。      网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c

A，实际应用：现实生活中经常需要计算某种方案的最小成本问题，比如希望利用最少量的电缆线连接一座建筑物中所有的计算机；再比如希望以最小的成本连接一个网络中的所有路由器等问题。把整个问题抽象成一个无向图，解决问题就是要构建一棵包含图中所有节点的树，并使构造出的树的总权值最小，即求解图的最小生成树问题。下面将介绍用于构造该种树的方法，Kruskal算法。 B，克鲁斯卡尔（Kruskal）算法：假设无向