注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1050】【HAOI2006】【旅行】  

2014-03-16 16:09:43|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     给出一个图,求S到T的所有路径中最大边与最小边比值的最大值。
     蒟蒻一看肯定就不会做= =,然后就各种spfa什么的乱yy。然后看了一些大众的题解是并查集,但是咱更感兴趣的便是 spfa的解法,然后没找到...(据说某博客说是有的(大雾),但是写的实在太不详细了)
     所以咱用的是并查集。思路显然是枚举每一条边作为这条路径的最大边,那么大于它的就可以删除了,然后贪心从它开始倒着加边,并合并并查集,直到s,t在同一个并查集里,然后这个时候最后加的那条边显然是最优的,更新答案即可。
     另外这题还有一个别名叫舒适的路线,可以去wikioi找到一个O(mlogm)的做法,但是表示没证明还是挺郁闷的....
======================================

program bzoj1050;
type edge=record
     u,v,w:longint;
     end;

var e:array[0..5010]of edge;
    f:array[0..5010]of longint;
    n,m,min,max,s,t:longint;
    ans:double;

function gcd(a,b:longint):longint;
begin
  if b=0 then exit(a) else exit(gcd(b,a mod b));
end;

procedure qsort(l,r:longint);
var i,j,x:longint;y:edge;
begin
  i:=l;j:=r;
  x:=e[(l+r)shr 1].w;
  repeat
    while e[i].w<x do inc(i);
    while e[j].w>x do dec(j);
    if i<=j then
     begin
       y:=e[i];e[i]:=e[j];e[j]:=y;
       inc(i);dec(j);
     end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

function find(x:longint):longint;
begin
  if f[x]=x then exit(x) else begin f[x]:=find(f[x]);exit(f[x]);end;
end;

procedure union(u,v:longint);begin f[u]:=v;end;

procedure init;
var i,j,u,v:longint;
begin
  read(n,m);
  for i:=1 to m do
   read(e[i].u,e[i].v,e[i].w);
  read(s,t);
  qsort(1,m);
  ans:=1e10;
  for i:=m downto 1 do
   begin
     for j:=1 to n do f[j]:=j;
     for j:=i downto 1 do
      begin
        u:=find(e[j].u);
        v:=find(e[j].v);
        if (u=v)then continue;
        union(u,v);
        u:=find(s);
        v:=find(t);
        if (u=v) then
          if (ans>e[i].w/e[j].w) then
           begin
             ans:=e[i].w/e[j].w;
             min:=e[j].w;
             max:=e[i].w;
           end;
      end;
   end;
  if ans=1e10 then write('IMPOSSIBLE')
              else
              if max mod min=0 then write(max div min)
               else write(max div gcd(min,max),'/',min div gcd(min,max));
end;

begin
  init;
end.



  评论这张
 
阅读(91)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017