题目大意:最小生成树
建源点0与各点连线的权为建水库的大小。
Program aa;
var
n,i,j,p:longint;
u,v,w:array[0..100000] of longint;
size,cost:longint;
father:array[0..300] of longint;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;j:=r;m:=w[(l+r) shr 1];
repeat
while w[i]<m do inc(i);
while w[j]>m do dec(j);
if i<=j then
begin
p:=w[i];w[i]:=w[j];w[j]:=p;
p:=u[i];u[i]:=u[j];u[j]:=p;
p:=v[i];v[i]:=v[j];v[j]:=p;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
begin
read(n);
for i:=1 to n do
begin
read(w[i]);
u[i]:=0;v[i]:=i;
end;
size:=n;
for i:=1 to n do
for j:=1 to n do
begin
read(p);
if i=j then continue;
inc(size);
u[size]:=i;v[size]:=j;w[size]:=p;
end;
qsort(1,size);
cost:=0;
for i:=0 to n do father[i]:=i;
for i:=1 to size do
begin
if (getfather(u[i])<>getfather(v[i])) then
begin
inc(cost,w[i]);
father[getfather(u[i])]:=father[getfather(v[i])];
end;
end;
writeln(cost);
end.
分享到:
相关推荐
最小生成树最小生成树最小生成树最小生成树最小生成树
头歌数据结构图的最小生成树算法 第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)...
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
最小生成树最小生成树最小生成树最小生成树最小生成树
问题描述:给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。基本要求:1、城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构定义采用课本中给出的定义...
最小生成树课程设计,给定一个地区的n个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。构造可以使n个城市连接的最小生成树
最小生成树计数的详细解题报告与C++代码~ 利用矩阵~
上窗体上有几个点,点击这些点形成连线,安最小生成树获得这些点的最小生成树
Prim最小生成树Prim最小生成树Prim最小生成树
最小生成树的构造,以及求最小生成树的 普利姆算法和克鲁斯卡尔算法,C++实现算法
如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题 2、利用克鲁斯卡尔算法求网的最小生成树; 3、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列; 4、输入为存在边的顶点对,以及它们之间...
采用堆排序实现带权值的边的顺序排列 利用克鲁斯卡尔算法实现最小生成树 首先 n城市之间全连接 输出所有连接和其边的权值 最后输出n个城市之间通信代价最小的最小生成树。 可用于java数据结构课程设计:“若要在n个...
最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++
利用克鲁斯卡尔算法求网的最小生成树。要求:若要在n各城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络,是一个网的最小生成树问题。
最小生成树问题时指在由m个节点和n条边组成的网络模型中寻找连接所有节点的生成树,使得其所有边的权值之和最小。最小生成树问题广泛应用于系统设计、选址规划等组合优化问题中。
关于构建最小生成树的实验报告,里面是C代码,有详细的过程描述,PRIM算法
(1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
多种方法求解最小生成树问题的PDF文件 赋权有向图的最小生成树算法; 基于Kruskal算法的最小生成树的构建; 普里姆算法和克鲁斯卡尔算法构造最小生成树; 用遗传算法求最小生成树等。
用最小生成树解决TSP问题 非常有用 输入各个城市坐标 可以输出路径