NKCITY – SPOJ

Đề bài: http://vn.spoj.com/problems/NKCITY/

Thuật toán:

• Giải bài này có thể sử dụng thuật toán Prim hoặc thuật toán Kruskal đều được.
• Các bạn có thể tham khảo cả 2 cách làm ở bên dưới.

Code:

Kruskal

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
        maxm    =10000;

type    data    =record
                u, v, c :longint;
                end;

var     f       :Text;
        n, m    :longint;
        Edges   :array[1..maxm] of Data;
        b       :Array[1..maxm] of longint;
        Father  :Array[1..maxn] of longint;
        res     :longint;
procedure nhap;
var     i, u, v, c :longint;
begin
        assign(f, fi);
        reset(f);
        readln(f, n, m);
        for i:=1 to m do
                begin
                        readln(f, u, v, c);
                        Edges[i].u:=u;
                        Edges[i].v:=v;
                        Edges[i].c:=c;
                end;
        close(f);
end;

Procedure init;
var     i :longint;
begin
        for i:=1 to m do b[i]:=i;
        for i:=1 to n do father[i]:=-1;
        res:=-1;
end;

procedure QS(l,r:longint);
var     i, j, x, tg     :longint;
begin
        i:=l;
        j:=r;
        x:=edges[b[ (l+r) div 2] ].c;
        repeat
                while Edges[b[i]].c < x do inc(i);
                while Edges[b[j]].c > x do dec(j);
                if i<=j then
                        begin
                                tg:=b[i];
                                b[i]:=b[j];
                                b[j]:=tg;
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l0 do t:=father[t];
        exit(t);
end;

procedure union(i, j:longint);
var     x :longint;
begin
        x:=father[i]+father[j];
        if father[i]>father[j] then
                begin
                        father[i]:=j;
                        father[j]:=x;
                end
        else    begin
                        father[j]:=i;
                        father[i]:=x;
                end;
end;

procedure Kruskal;
var     i, u,v, c, r1, r2 :longint;
begin
        init;
        QS(1,m);
        for i:=1 to m do
                begin
                        u:=Edges[b[i]].u;
                        v:=Edges[b[i]].v;
                        c:=Edges[b[i]].c;
                        r1:=find(u);
                        r2:=find(v);
                        if r1<>r2 then
                                begin
                                        union(r1,r2);
                                        res:=max(res,c);
                                end;
                end;
end;

procedure xuat;
begin
        assign(f, fo);
        rewrite(f);
        writeln(f, res);
        close(f);
end;

BEGIN
        nhap;
        Kruskal;
        xuat;
END.

Prim

const   fi='';
        fo='';
        maxn=1000;
        maxc=trunc(1e9);
var     d:array[1..maxn] of longint;
        i,j,n,m,res:longint;
        u,v,t:longint;
        cx:array[1..maxn] of boolean;
        c:array[1..maxn,1..maxn] of longint;
procedure init;
begin
    for i:=1 to n do d[i]:=maxc;
    d[1]:=0;
    fillchar(cx,sizeof(cx),true);
end;
procedure prim;
var     min,u:longint;
begin
        repeat
                min:=maxc;u:=0;
                for i:=1 to n do
                        if cx[i] then
                        if d[i]res then res:=d[u];
                for v:=1 to n do
                        if cx[v] then
                                if d[v]>c[u,v] then
                                        begin
                                            d[v]:=c[u,v];
                                        end;
        until false;
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    readln(n,m);
    for i:=1 to n do
        for j:=1 to n do
                if i<>j then c[i,j]:=maxc else c[i,j]:=0;
    for i:=1 to m do
        begin
            readln(u,v,t);
            c[u,v]:=t;
            c[v,u]:=t;
        end;
    init;
    prim;
    writeln(res);
    close(input);close(output);
end.