CODEVS1001 舒适的路线 (并查集)

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

program CODEVS1001;
const maxm=;
maxn=;
INF=;
type arr=record
u,v,w:int64;
end;
var eg:array[..maxm] of arr;
fa:array[..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 ].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-;
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= then exit(x) else exit(gcd(y,x mod y));
end;
begin
readln(n,m);
j:=;
for i:= to m do
begin
readln(x,y,z);
add(x,y,z);
end;
readln(s,t);
sort(,m);
ans1:=INF;
ans2:=-INF;
for i:= to m do
begin
for j:= 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]舒适的路线


下一篇:关于H5的Canvas