没用的话：好像很久没发博客了，主要是懒太蒟找不到水题。我绝对没弃坑...^_^
还用些话：本文为博主原创文章，若转载请注明原网址和作者。
进入正题：
先pa网址： bzoj ：http://www.lydsy.com/JudgeOnline/problem.php?id=1050
codevs.cn：http://codevs.cn/problem/1001/
题目描述就放bzoj的(主要是为了配合标题)(ps:codevs和bzoj的题目描述不一样)。
Description
给你一个无向图，N(N<=500)个顶点, M(M<=5000)条边，每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T
，求一条路径，使得路径上最大边和最小边的比值最小。如果S和T之间没有路径，输出”IMPOSSIBLE”，否则输出这个比值，如果需要，表示成一个既约分数。 备注： 两个顶点之间可能有多条路径。
(其实我A完这题还不知道这图有何用,我猜测这图是来旅游的放错位置了)
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<=5000Output
如果景点s到景点t没有路径，输出“IMPOSSIBLE”。否则输出一个数，表示最小的速度比。如果需要，输出一
个既约分数。Sample Input
Sample Output
思路：其实一开始一点思路都没有，就想spfa乱搞，结果A了1个点（我不会告诉你那个点是“IMPOSSIBLE”）。
听到大神犇 QZZ 和 ZN 说什么并查集,不管说什么，膜就对了！！！
Orz！Orz！Orz！Orz！Orz！Orz！Orz！Orz！Orz！
然后蒟蒻我就默默看了题解我认认真真地思(kan)考(le)了(ti)下(jie)。不要在意括号说了什么！！认真看了，下面才是重点，上面只是凑个字数。
大概就是：1、按边权(v[i])从小到大(其实从大到小也可以,自己去乱搞)排序。
2、从大到小枚举边，记录max（最大权值，因为排序，所以max=v[当前枚举的边的编号]）。
3、再来一重枚举从大（当前枚举的边）到小，用并查集合并 x,y 节点，主要是用来判断合并后 s(起点),t(终点) 是否联通。
4、判断 s,t 联通后就可以来更新答案（最大速度和最小速度的比值），并记录最大速度和最小速度。
5、约分输出答案。
基本上是这样做的。
下面就代码：
pascal：
var n,m,s,t:longint; i,j:longint; father,x,y,v:array[0..10000]of longint; ans:real; //用来储存最大速度和最小速度的比值 ansmax,ansmin,min,max:longint;//分别为 最大速度 最小速度 枚举到的最小速度 枚举到的最大速度 gcdxy:longint;//最大公因数,为了约分function getfather(x:longint):longint;//并查集找祖先begin if father[x]=x then exit(x) else begin father[x]:=getfather(father[x]); getfather:=father[x]; end;end;procedure join(x,y:longint);//并查集合并var fx,fy:longint;begin fx:=getfather(x); fy:=getfather(y); if fx<>fy then father[fx]:=fy;end;function gcd(x,y:longint):longint;//最大公因数begin if y=0 then exit(x) else exit(gcd(y,x mod y));end; procedure qs(l,r:longint);//快排var i,j,t,m:longint;begin i:=l; j:=r; m:=v[(l+r) >> 1]; repeat while v[i]m do dec(j); if i<=j then begin t:=v[i];v[i]:=v[j];v[j]:=t; t:=x[i];x[i]:=x[j];x[j]:=t; t:=y[i];y[i]:=y[j];y[j]:=t; inc(i); dec(j); end; until i>j; if l max/min then //答案更优就更新 begin ans:=max/min; ansmax:=max; ansmin:=min; end; end; end; end; if ansmin=0 then //如果最大速度或最小速度还都为0 说明都没更新过，所以 s,t 无法联通 begin writeln('IMPOSSIBLE'); exit; end; gcdxy:=gcd(ansmax,ansmin); //最大公约数+约分 就不说了吧 if gcdxy=ansmin then writeln(ansmax div ansmin) else writeln(ansmax div gcdxy,'/',ansmin div gcdxy);end.
一直都是这样啦,c++ 有时间再补上！！
然后蒟蒻我又水了一篇博客。