首页 > 代码库 > BZOJ 1050： [HAOI2006]旅行comf（枚举+并查集）
BZOJ 1050： [HAOI2006]旅行comf（枚举+并查集）
[HAOI2006]旅行comf
Description
给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T
，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出
这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。
Input
第一行包含两个正整数，N和M。下来的M行每行包含三个正整数：x，y和v。表示景点x到景点y之间有一条双向
公路，车辆必须以速度v在该公路上行驶。最后一行包含两个正整数s，t，表示想知道从景点s到景点t最大最小速
度比最小的路径。s和t不可能相同。
1<N<=500,1<=x,y<=N，0<v<30000，0<M<=5000
Output
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一
个既约分数。
Sample Input
【样例输入1】
4 2
1 2 1
3 4 2
1 4
【样例输入2】
3 3
1 2 10
1 2 5
2 3 8
1 3
【样例输入3】
3 2
1 2 2
2 3 4
1 3
Sample Output
【样例输出1】
IMPOSSIBLE
【样例输出2】
5/4
【样例输出3】
2
分析:
由于结果关系到两个因素最大边和最小边，我们先排序然后可以枚举最小边，然后将小于改变的全部边忽略，找出该情况下起点到终点路径上最小的最大边，可以用spfa做，不过会比较慢，其实可以并查集，按从小到大的顺序将符合要求的边进行并查集处理，当s和t位于同一集合中时终止，当前的边为最小的最大边。然后找出比值max的即可。
代码：
program comf;var f:array[0..500]of longint; a,b,c:array[0..5000]of longint; n,i,m,l,r,s,t,ans,j,x,y:longint;function gcd(x,y:longint):longint;var r:longint;begin r:=x mod y; while r<>0 do begin x:=y; y:=r; r:=x mod y; end; exit(y);end;function find(x:longint):longint;var i,j,k:longint;begin i:=x; j:=x; while i<>f[i] do i:=f[i]; while i<>j do begin k:=f[j]; f[j]:=i; j:=k; end; exit(i);end;procedure cheak(x,y:longint);var t:longint;begin if x*r<y*l then begin t:=gcd(x,y); l:=x div t; r:=y div t; end;end;procedure qsort(l,h:longint);var i,j,t,m:longint;begin i:=l; j:=h; m:=c[(i+j) div 2]; repeatwhile c[i]<m do inc(i);while m<c[j] do dec(j);if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t;t:=b[i]; b[i]:=b[j]; b[j]:=t; t:=c[i]; c[i]:=c[j]; c[j]:=t;inc(i); dec(j); end; until i>j; if i<h then qsort(i,h); if j>l then qsort(l,j); end;begin readln(n,m); for i:=1 to m do readln(a[i],b[i],c[i]); qsort(1,m); l:=2; r:=0; readln(s,t); for i:=1 to m do begin ans:=-1; for j:=1 to n do f[j]:=j; for j:=i to m do begin x:=find(a[j]); y:=find(b[j]); f[y]:=x; x:=find(s); y:=find(t); if x=y then begin ans:=j; break; end; end; if ans>-1 then cheak(c[ans],c[i]); end; if r=0 then writeln(‘IMPOSSIBLE‘) else if r=1 then writeln(l) else writeln(l,‘/‘,r); end.
BZOJ 1050： [HAOI2006]旅行comf（枚举+并查集）