Trở về đầu

foto1 foto2 foto3 foto4 foto5
Nguyễn Tô Sơn - Giảng viên Đại học Sư phạm Hà Nội. SĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành tích hôm nay, Thành công ngày mai !

Tìm kiếm

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 = 'KRUSKAL.INP';
      fo = 'KRUSKAL.OUT';
      MAXN = 1000;
      MAXM = 10000;

var n, m, dem: integer;
    u, v, c: array [1..MAXM] of integer;
    vung: array [1..MAXN] of integer;
    //g: array [1..3, 1..MAXM] of integer;
    //g[1, i] = u[i]
    //g[2, i] = v[i]
    //g[3, i] = c[i]
    f: text;

procedure Nhap;
var i, j: integer;
begin
        assign(f, fi); reset(f);
        readln(f, n, m);
        for i:= 1 to m do readln(f, u[i], v[i], c[i]);
        close(f);
end;

procedure DoiCho(var a, b: integer);
var tg: integer;
begin
        tg:= a;
        a:= b;
        b:= tg;
end;

procedure SapXep;
var i, j: integer;
begin
        for i:= 1 to m-1 do
                for j:= i+1 to m do
                        if c[i] > c[j] then
                        begin
                                DoiCho(u[i], u[j]);
                                DoiCho(v[i], v[j]);
                                DoiCho(c[i], c[j]);
                        end;
end;

procedure Init;
var i: integer;
begin
        for i:= 1 to n do vung[i]:= i;
end;

procedure Kruskal;
var i, tong, dem: integer;
begin
        // Nhanh trong truong hop m > n
        assign(f, fo); rewrite(f);
        tong:= 0;
        dem:= 0;
        for i:= 1 to m do
                if vung[u[i]] <> vung[v[i]] then   // Dieu kien khong tao thanh chu trinh
                begin
                        writeln(f, '(', u[i], ', ', v[i], ')');
                        inc(dem);
                        tong:= tong + c[i];
                        if dem = n-1 then break;
                        vung[v[i]]:= vung[u[i]];
                        // De lam cho u[i] va v[i] lien thong voi nhau
                end;
        writeln(f, tong);
        close(f);


end;

BEGIN
        Nhap;
        SapXep;
        Init;
        Kruskal;
END.

Bản quyền thuộc về Nguyễn Tô Sơn, Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869