首页 > 代码库 > 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 舒适的路线 (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。