专栏首页HansBug's Lab1050: [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        

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2929: [Poi1999]洞穴攀行

    2929: [Poi1999]洞穴攀行 Time Limit: 1 Sec  Memory Limit: 128 MB Submit: 80  Solved: ...

    HansBug
  • 1934: [Shoi2007]Vote 善意的投票

    1934: [Shoi2007]Vote 善意的投票 Time Limit: 1 Sec  Memory Limit: 64 MB Submit: 1174  ...

    HansBug
  • 2243: [SDOI2011]染色

    2243: [SDOI2011]染色 Time Limit: 20 Sec  Memory Limit: 512 MB Submit: 3113  Solved...

    HansBug
  • 2761: [JLOI2011]不重复数字(平衡树)

    2761: [JLOI2011]不重复数字 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 2133  So...

    HansBug
  • 1901: Zju2112 Dynamic Rankings

    1901: Zju2112 Dynamic Rankings Time Limit: 10 Sec  Memory Limit: 128 MB Submit: ...

    HansBug
  • 算法模板——线段树8 (字符串回文变换)

    实现功能:输入一个长度为N的由26个大写字母组成的字符串,输入M条指令:"1 x y",将x到y的字串重组构成一个字典序最小的回文串,如果不能构成回文串输出Fa...

    HansBug
  • Daydream View + Pixel 2初体验,意料之中的进步

    VRPinea
  • 如何制作圆形头像或图片

    原理:我们利用Photoshop的椭圆选区工具,将未选择的区域删除,就得到了我们想要的效果啦。

    乐心湖
  • Linux 命令行快捷键

    在操作Linux的时候,有的时候从其他地方copy一段命令,发现前面多了东西或少了东西,要移动左右键到最前面,改完再移动到最后面,真是麻烦至极,幸好有快捷键,来...

    互扯程序
  • 李磊:从底层研发“敦煌”让我受益匪浅

    LiveVideoStack:李磊你好,简单介绍下自己的工作经历,以及在美摄负责的工作内容和专注的领域。

    LiveVideoStack

扫码关注云+社区

领取腾讯云代金券