HỌC TIN CÙNG THỦ KHOA

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.