【NOIP2017练习】论战大原题（并查集）

题意：给定一个n个点m条边的无向图。定义一条路径的长度为路径上最小边的权值。

定义dist(i,j)为起点为i，终点为j的长度最长的路径的长度。求出第k大的dist(i,j)(i<j)。

对于所有的数据，保证n≤100000，m≤min(n^2,200000)，k≤n(n-1)/2且图连通，w≤10^9。

思路：lyy去年出的题

var a,b,c,fa:array[1..300000]of longint;
    size:array[1..300000]of int64;
    n,m,i,u,v:longint;
    k:int64;

procedure swap(var x,y:longint);
var t:longint;
begin
 t:=x; x:=y; y:=t;
end;

procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
 i:=l; j:=r; mid:=c[(l+r)>>1];
 repeat
  while mid<c[i] do inc(i);
  while mid>c[j] do dec(j);
  if i<=j then
  begin
   swap(a[i],a[j]);
   swap(b[i],b[j]);
   swap(c[i],c[j]);
   inc(i); dec(j);
  end;
 until i>j;
 if l<j then qsort(l,j);
 if i<r then qsort(i,r);
end;

function find(k:longint):longint;
begin
 if k<>fa[k] then fa[k]:=find(fa[k]);
 exit(fa[k]);
end;

begin
 assign(input,'original.in'); reset(input);
 assign(output,'original.out'); rewrite(output);
 readln(n,m,k);
 for i:=1 to m do readln(a[i],b[i],c[i]);
 for i:=1 to n do
 begin
  size[i]:=1; fa[i]:=i;
 end;
 qsort(1,m);
 for i:=1 to m do
 begin
  u:=find(a[i]); v:=find(b[i]);
  if u<>v then
  begin
   k:=k-size[u]*size[v];
   fa[v]:=u; size[u]:=size[u]+size[v];
  end;
  if k<=0 then
  begin
   writeln(c[i]);
   break;
  end;
 end;


 close(input);
 close(output);
end.