NKCITY - Xây dựng thành phố

Tác giả: ladpro98

Ngôn ngữ: Pascal

program nkcity;
uses    math;
type    e=record
        v,w,link:longint;
        end;
const   fi='';
        maxm=23456;
        maxn=2345;

var     adj:array[1..maxm] of e;
        head:array[1..maxn] of longint;
        avail:array[1..maxn] of boolean;
        q:array[1..maxm] of longint;
        n,m,mm,maxW,res:longint;

procedure input;
var     inp:text;
        i,x,y,w:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,mm);
        for i:=1 to mm do
        begin
                readln(inp,x,y,w);
                inc(m);
                adj[m].v:=y;
                adj[m].w:=w;
                adj[m].link:=head[x];
                head[x]:=m;
                inc(m);
                adj[m].v:=x;
                adj[m].w:=w;
                adj[m].link:=head[y];
                head[y]:=m;
                maxW:=max(maxW,w);
        end;
        close(inp);
end;

function bfs(lim:longint):boolean;
var     l,r,i,u:longint;
begin
        for i:=1 to n do
        avail[i]:=true;
        l:=1;r:=1;
        q[1]:=1;avail[1]:=false;
        while l<=r do
        begin
                u:=q[l];inc(l);
                i:=head[u];
                while i>0 do
                begin
                        if (adj[i].w<=lim) and (avail[adj[i].v]) then
                        begin
                                inc(r);
                                q[r]:=adj[i].v;
                                avail[adj[i].v]:=false;
                        end;
                        i:=adj[i].link;
                end;
        end;
        for i:=1 to n do
        if avail[i] then exit(false);
        exit(true);
end;

procedure process;
var     l,r,m:longint;
begin
        l:=1;r:=maxW;
        while l<=r do
        begin
                m:=(l+r) div 2;
                if bfs(m) then
                begin
                        res:=m;
                        r:=m-1;
                end
                else    l:=m+1;
        end;
end;

begin
        input;
        process;
        write(res);
end.

Download