FWATER - Tưới nước đồng cỏ
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program FWATER;
Const
input = '';
output = '';
maxn = 300;
maxc = 100000000;
Var
a: array[0..maxn,0..maxn] of integer;
d,trace: array[0..maxn] of integer;
free: array[0..maxn] of boolean;
w: array[1..maxn] of integer;
n: integer;
Procedure init;
Var
f: text;
i,j: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n);
For i:= 1 to n do
Begin
readln(f, a[0,i]);
a[i,0]:= a[0,i];
End;
For i:= 1 to n do
For j:= 1 to n do read(f, a[i,j]);
Close(f);
End;
Procedure Prim;
Var
u,v,i,k,min: integer;
Begin
Fillchar(free, sizeof(free), true);
For i:= 1 to n do d[i]:= maxc;
d[0]:= 0;
For k:= 0 to n do
Begin
u:= -1;
min:= maxc;
For i:= 0 to n do
if free[i] and (d[i] < min) then
Begin
min:= d[i];
u:= i;
End;
free[u]:= false;
For v:= 0 to n do
if free[v] and (d[v] > a[u,v]) then
Begin
d[v]:= a[u,v];
trace[v]:= u;
End;
End;
End;
Procedure printresult;
Var
f: text;
i,res: integer;
Begin
Assign(f, output);
Rewrite(f);
res:= 0;
For i:= 1 to n do res:= res + a[trace[i],i];
Writeln(f, res);
Close(f);
End;
Begin
init;
Prim;
printresult;
End.