传送门 二分答案。 显然我们应该尽可能的选择能选的一级公路。 如果不能选再选二级公路。 判断方案是否可行即可。
var a,b,c,d,f:array [0..30005] of longint; n,m,k,i,l,r,mi:longint; function get(x:longint):longint; begin if f[x]=x then exit(x); f[x]:=get(f[x]); exit(f[x]); end; function jud(mi:longint):boolean; var i,s,p,q:longint; begin s:=0; for i:=1 to n do f[i]:=i; for i:=1 to m do if c[i]<=mi then begin p:=get(a[i]); q:=get(b[i]); if p<>q then begin f[p]:=q; inc(s); end; end; if s<k then exit(false); for i:=1 to m do if d[i]<=mi then begin p:=get(a[i]); q:=get(b[i]); if p<>q then begin f[p]:=q; inc(s); end; end; if s<>n-1 then exit(false) else exit(true); end; begin read(n,k,m); dec(m); for i:=1 to m do read(a[i],b[i],c[i],d[i]); l:=1; r:=30000; while l<r do begin mi:=(l+r) div 2; if jud(mi) then r:=mi else l:=mi+1; end; write(l); end.