Trở về đầu
Mời các bạn Download code tại: Click here
1. File Input: Click here
- Dòng đầu tiên gồm 2 số n và m tương ứng là số đỉnh và số cạnh của đồ thị.
- m dòng tiếp theo mỗi dòng gồm 3 số là u, v, c tương ứng là đỉnh đầu, đỉnh cuối và trọng số của một cạnh của đồ thị
2. File Output
- Gồm nhiều dòng, mỗi dòng 2 số u, v tương ứng là đỉnh đầu và đỉnh cuối của cạnh nằm trong cây khung nhỏ nhất.
- Dòng cuối cùng ghi trọng số của cây khung nhỏ nhất tìm được.
const fi = 'PRIM.INP';
fo = 'PRIM.OUT';
MAXN = 1000;
MAXM = 10000;
oo = MAXINT;
var n, m: integer;
a: array [1..MAXN, 1..MAXN] of integer;
cx: array [1..MAXN] of boolean;
f: text;
procedure Nhap;
var i, u, v, c: integer;
begin
assign(f, fi); reset(f);
readln(f, n, m);
fillchar(a, sizeof(a), 0);
for i:= 1 to m do
begin
readln(f, u, v, c);
a[u, v]:= c;
a[v, u]:= c;
end;
close(f);
end;
procedure Tim(var i, j, min: integer);
var x, y: integer;
begin
min:= +oo;
for x:= 1 to n do
if cx[x] = false then
for y:= 1 to n do
if cx[y] = true then
if a[x, y] > 0 then
if min > a[x, y] then
begin
i:= x;
j:= y;
min:= a[x, y];
end;
end;
procedure Prim;
var tong, i, j, k, min: integer;
begin
for i:= 1 to n do cx[i]:= true;
cx[1]:= false;
tong:= 0;
assign(f, fo); rewrite(f);
for k:= 1 to n-1 do
begin
Tim(i, j, min);
writeln(f, '(', i, ', ', j, ')');
cx[j]:= false;
tong:= tong + min;
end;
writeln(f, tong);
close(f);
end;
BEGIN
Nhap;
Prim;
END.