CODEVS1001 舒适的路线 （并查集）

对所有边从大到小排序，枚举最大边，O（m）验证，用并查集维护图是否联通。

program CODEVS1001;
const maxm=5008;
      maxn=508;
      INF=2000000000;
type arr=record
      u,v,w:int64;
      end;
var eg:array[0..maxm] of arr;
    fa:array[0..maxn] of longint;
    i,j,m,n,x,y,z,s,t,u,v,d:longint;
        ans1,ans2:int64;
procedure add(u,v,w:longint);
begin
  inc(j);
  eg[j].u:=u;
  eg[j].v:=v;
  eg[j].w:=w;
end;
 procedure sort(l,r: longint);
      var
         i,j,x: longint;
         y:arr;
      begin
         i:=l;
         j:=r;
         x:=eg[(l+r) div 2].w;
         repeat
           while eg[i].w>x do
            inc(i);
           while x>eg[j].w do
            dec(j);
           if not(i>j) then
             begin
                y:=eg[i];
                eg[i]:=eg[j];
                eg[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
function find(x:longint):longint;
begin
  if fa[x]=x then exit(x);
  fa[x]:=find(fa[x]);
  exit(fa[x]);
end;
function gcd(x,y:longint):longint;
begin
  if y=0 then exit(x) else exit(gcd(y,x mod y));
end;
begin
  readln(n,m);
  j:=0;
  for i:=1 to m do
    begin
      readln(x,y,z);
      add(x,y,z);
    end;
  readln(s,t);
  sort(1,m);
  ans1:=INF;
  ans2:=-INF;
  for i:=1 to m do
    begin
      for j:=1 to n do fa[j]:=j;
      for j:=i to m do
        begin
          u:=eg[j].u; v:=eg[j].v;
          x:=find(u);
          y:=find(v);
          if x<>y then
            begin
              fa[x]:=y;
              if find(fa[s])=find(fa[t]) then
                begin
                  if eg[i].w*ans2<eg[j].w*ans1 then
                    begin
                      ans1:=eg[i].w;
                      ans2:=eg[j].w;
                    end;
                  continue;
                end;
            end;
        end;
    end;
  d:=gcd(ans1,ans2);
  if ans1=INF then writeln('IMPOSSIBLE') else
    if d=ans2 then writeln(ans1 div ans2) else
      writeln(ans1 div d,'/',ans2 div d);
end.