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.