首页 > 代码库 > 1050: [HAOI2006]旅行comf

1050: [HAOI2006]旅行comf

1050: [HAOI2006]旅行comf

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 1495  Solved: 737
[Submit][Status]

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不可能相同。

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

HINT

 

【数据范围】

1<  N < = 500

1 < = x, y < = N,0 < v < 30000,x ≠ y

0 < M < =5000

 

Source

 

 题解:这个题嘛,害得我想了好久才发现可以模仿kruskal最小生成树的思想(phile:汗。。。),具体如下——先是将所有的边排个序,然后枚举一个数对(i,j)(i<=j)即当从第i边开始用时,只需要一直用到第j个边既可以使s和t联通(由于边已经排了序,所以这样子能保证对于每个i,j均是最优解),然后这样子跑N次,打擂台取出最小值就可以了——Accept 4860ms(HansBug:是不是太慢了点 *_*)
 
  1 var  2    i,j,k,l,m,n,s,t:longint;  3    mx,my,mm:int64;  4    a:array[0..10000,1..3] of longint;  5    c:array[0..1000] of longint;  6 function max(x,y:longint):longint;inline;  7          begin  8               if x>y then max:=x else max:=y;  9          end; 10 function min(x,y:longint):longint;inline; 11          begin 12               if x<y then min:=x else min:=y; 13          end; 14 function getfat(x:longint):longint;inline; 15          begin 16               while x<>c[x] do x:=c[x]; 17               getfat:=x; 18          end; 19 procedure startset(x:longint);inline; 20           var i:longint; 21           begin 22                for i:=1 to x do c[i]:=i; 23           end; 24 function tog(x,y:longint):boolean; inline; 25          begin 26               exit(getfat(x)=getfat(y)); 27          end; 28 procedure merge(x,y:longint);inline; 29           begin 30                c[getfat(x)]:=getfat(y); 31           end; 32 procedure swap(var x,y:longint);inline; 33           var z:longint; 34           begin 35                z:=x;x:=y;y:=z; 36           end; 37 procedure sort(l,r:longint); 38           var i,j,x,y:longint; 39           begin 40                i:=l;j:=r;x:=a[(l+r) div 2,3]; 41                repeat 42                      while a[i,3]<x do inc(i); 43                      while a[j,3]>x do dec(j); 44                      if i<=j then 45                         begin 46                              swap(a[i,1],a[j,1]); 47                              swap(a[i,2],a[j,2]); 48                              swap(a[i,3],a[j,3]); 49                              inc(i);dec(j); 50                         end; 51                until i>j; 52                if l<j then sort(l,j); 53                if i<r then sort(i,r); 54           end; 55 function gcd(x,y:int64):int64; 56          var z:int64; 57          begin 58               while y<>0 do 59                     begin 60                          z:=x mod y; 61                          x:=y; 62                          y:=z; 63                     end; 64               exit(x); 65          end; 66  67 begin 68      readln(n,m); 69      for i:=1 to m do readln(a[i,1],a[i,2],a[i,3]); 70      readln(s,t); 71      sort(1,m); 72      mx:=1;my:=maxlongint; 73      for i:=1 to m do 74          begin 75               startset(n); 76               for j:=i to m do 77                   begin 78                        if tog(a[j,1],a[j,2]) then continue; 79                        merge(a[j,1],a[j,2]); 80                        if tog(s,t) then 81                           begin 82                                if (my*a[i,3])>(mx*a[j,3]) then 83                                   begin 84                                        my:=a[j,3]; 85                                        mx:=a[i,3]; 86                                   end; 87                                break; 88                           end; 89                   end; 90          end; 91      if (my=maxlongint) and (mx=1) then 92         begin 93              writeln(IMPOSSIBLE); 94              halt; 95         end; 96      mm:=gcd(mx,my); 97      mx:=mx div mm; 98      my:=my div mm; 99 100      if mx=1 then writeln(my) else writeln(my,/,mx);101 end.102        

 

1050: [HAOI2006]旅行comf