1003 电话连线
题目描述 Description
一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。
输入描述 Input Description
输入文件的第一行是n的值（n<=100）.
第二行至第n+1行是一个n*n的矩阵，第i行第j列的数如果为0表示城市i与城市j有电话线连接，否则为这两个城市之间的连接费用（范围不超过10000）。
输出描述 Output Description
输出文件的第一行为你连接的电话线总数m，第二行至第m+1行为你连接的每条电话线，格式为i j，（i<j）， i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出，起始点为1.
第m+2行是连接这些电话线的总费用。
样例输入 Sample Input
5
0 15 27 6 0
15 0 33 19 11
27 33 0 0 17
6 19 0 0 9
0 11 17 9 0
样例输出 Sample Output
2
1 4
2 5
17
数据范围及提示 Data Size & Hint
n<=100
个人解法：
很显然的是Prim。
只是说说需要做的操作怎么实现。
首先，在我们更新最小生成树的时候，会有一条边的权值。这条权值如果是0，则表明这条边是给出的，不必工程费。而如果边权不为0，则说明我们必须要花钱去买。
接下来，对于总权值的计算就是就是所有最小生成树边权加起来。
而对于路径输出，个人是用的数组储存，对于一条权值不为0的边，就记录下来。之后按顺序输出即可。
这么久没有打Prim，复习复习图论。
代码如下：
type
inf=record
x,y:longint;//一个存边的玩意
end;
var
path:array[1..100,1..100] of longint;
dist,last:array[1..100] of longint;//last[i]记录节点i是由哪一个点更新而来的。
e:array[1..100] of inf;
flag:array[1..100] of boolean;
n,sum,top:longint;
procedure linit;//初始化
var
vi,vj,w:longint;
begin
read(n);
for vi:=1 to n do
for vj:=1 to n do
read(path[vi,vj]);
end;
procedure prim(vi:longint);//Prim算法
var
vj,vk,min,p:longint;
begin
for vj:=1 to n do
begin
dist[vj]:=path[vi,vj];
last[vj]:=vi;
end;
flag[vi]:=true;
for vj:=1 to n-1 do
begin
min:=maxlongint;
for vk:=1 to n do
if (dist[vk]<min) and (not flag[vk]) then
begin
p:=vk;
min:=dist[vk];
end;
flag[p]:=true;
if dist[p]<>0 then
begin
inc(sum,min);//更新费用
inc(top);//统计边数
if last[p]<p then
begin
e[top].x:=last[p];//用last[p]与p确定一条线段
e[top].y:=p;
end
else
begin
e[top].x:=p;
e[top].y:=last[p];
end;
end;
for vk:=1 to n do
if dist[vk]>path[p,vk] then
begin
dist[vk]:=path[p,vk];
last[vk]:=p;//更新last
end;
end;
end;
procedure print;//输出
var
vi:longint;
begin
writeln(top);//输出边数
for vi:=1 to top do
writeln(e[vi].x,' ',e[vi].y);//输出边
writeln(sum);//输出总费用
end;
begin
linit;//初始化
prim(1);//最小生成树
print;
end.
多年未打prim，复习一下就好。