首页 > 代码库 > CODEVS1001 舒适的路线 (并查集)

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.

 

CODEVS1001 舒适的路线 (并查集)