2 1 0
[样例输出]
2(注:表示连接1和2,2和3,费用为2)
[问题分析]
本题是典型的求图的最小生成树问题,我们可以利用Prim算法或者Kruskal算法求出,下面的
程序在数据结构上对Kruskal算法做了一点修改,具体细节请看程序及注解。
[参考程序]
Program wire(Input, Output);
var g : Array [1..100, 1..100] Of Integer;{邻接矩阵}
l : Array [0..100] Of Integer; {l[i]存放顶点i到当前已建成的生成树中
任意一顶点j的权值g[i,j]的最小值}
u : Array [0..100] Of Boolean; { u[i]=True,表示顶点i还未加入到生成树中;
u[i]=False,表示顶点I已加入到生成树中
}
n, i, j, k, total : Integer;
Begin
Assign(Input, 'wire.in');
Reset(Input);
Assign(Output, 'wire.out');
Rewrite(Output);
Readln(n);
For i := 1 To n Do Begin
For j := 1 To n Do Read(g[i,j]);
Readln;
End;
Fillchar(l, sizeof(l), $7F); {初始化为maxint}
l[1] := 0; {开始时生成树中只有第1个顶点}
Fillchar(u, sizeof(u), 1); {初始化为True,表示所有顶点均未加入}
For i := 1 To n Do
Begin
k := 0;
For j := 1 To n Do {找一个未加入到生成树中的顶点,记为k,
要求k到当前生成树中所有顶点的代价最小}
If u[j] And (l[j] < l[k]) Then k := j;
u[k] := False; {顶点k加入生成树}
For j := 1 To n Do {找到生成树中的顶点j,要求g[k,j]最小}
If u[j] And (g[k,j] < l[j]) Then l[j] := g[k,j];
End;
total := 0;
For i := 1 To n Do Inc(total, l[i]); {累加}
Writeln(total);
Close(Input);
Close(Output);
第 5 页 共 23 页