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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1486】【Hnoi2009】【最小圈】  

2014-04-29 19:45:08|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    题目大意:给出一个带权有向图,求出这个图的圈的平均长度的最小值。
    做法也比较经典...就不说了,即直接二分答案,把这个图的所有边都减去这个答案,然后如果有负环就说明是存在的。
    = =但是问题就是如何判断原图有负环,一开始咱是用的spfa判断负环,但是发现...要每一个点都跑一次Spfa,复杂度大概O(kNM),这个是肯定过不了的...【尤其是那个k...】,所以TLE了一次...然后咱们需要在更快的时间找到负环...
    0.0咱太弱了不知道怎么找...然后参考了Dmute君的题解:【传送门
    首先要证明的性质就是这个:
   【负环上必然存在一个点,沿着负环走始终走过的距离是负的】
   【这个还没有证明出来的,{}的请无视】
    {
    咱们假设没有这样一个点吧,咱们先随意挑一个点,然后走一圈变成了负数的话,咱们考虑最后那一条边,由于这样一个性质,没有这样一个点,也就是说考虑一个点i,它有:
    存在∑w[u,v]>0 (u,v取遍除了i和它的前驱的点的所有点对)
    ∑w[u,v]<0 (u,v取遍所有点对)
    但是这是不可能的,因为对于其他点,实际上它们的所有路径都可以看做到i的路径+i的所有路径,如果都有这个性质的话,则有
    }
    当咱们证明了这个,咱们就会发现,咱们需要做的只是在每一次DFS,然后DFS的时候只沿着能使得距离为负权的边走,然后这样子复杂度就减少了很多。一个负权环最多O(n)个点,然后由于每一次只找负权边,所以一次搜索大概O(n^3),但是上界略松,所以就可以ac了
    最后弄一下精度即可。
========================

program bzoj1486; const eps=1e-10; inf=1e10; maxn=50010; type edge=record v,pre:longint; w,cap:double; end; var e:array[0..200010]of edge; last,que,ti:array[0..50100]of longint; dist:array[0..50100]of double; v:array[0..50100]of boolean; tot,n,m:longint; flag:boolean; procedure addedge(u,v:longint;w:double); begin inc(tot);e[tot].v:=v;e[tot].w:=w; e[tot].pre:=last[u];last[u]:=tot; e[tot].cap:=w; end; procedure dfs(p:longint;w:double); var tmp:longint; begin tmp:=last[p]; while tmp<>0 do begin if dist[p]+e[tmp].w-w+eps<dist[e[tmp].v] then begin if not v[e[tmp].v] then begin v[e[tmp].v]:=true; dist[e[tmp].v]:=dist[p]+e[tmp].w-w; dfs(e[tmp].v,w); v[e[tmp].v]:=false; if flag then exit; end else begin flag:=true; exit; end; end; tmp:=e[tmp].pre; end; end; function pd(w:double):boolean; var i:longint; begin flag:=false; fillchar(v,sizeof(v),false); for i:=1 to n do dist[i]:=0.0; for i:=1 to n do begin v[i]:=true; dfs(i,w); v[i]:=false; if flag then break; end; exit(flag); end; procedure init; var i,u,v:longint; w,l,r,mid:double; begin read(n,m); tot:=0; fillchar(last,sizeof(last),0); for i:=1 to m do begin read(u,v,w); addedge(u,v,w); if i=1 then begin l:=w;r:=w; end else begin if l>w then l:=w; if r<w then r:=w; end; end; while l+eps<r do begin mid:=(l+r)/2; if pd(mid) then r:=mid else l:=mid; end; writeln(l:0:8); end; begin init; end.
  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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