1. 首页
  2. 网络流

HDU 5988 Coding Contest (费用流)

题意:在n个点上有着食物,有m条边,除了第一个走的人,其他人都有pi的概率这条边,再大家都能获得食物的前提下,求破坏网络的概率最小。

思路:

每条边有走的次数(流量),每条边走一次发生破坏概率为p(流量1,费用p),容易想到费用流。可是费用流往往是费用相加的,这个是概率,只能相乘。有什么办法,log函数可以把乘除法转换为加减法。所以对每个概率取个log当成费用就行了。

log取底数取个2,然后对每条边的概率值取个对数,跑一次最小费用流,感觉没什么问题,但是会wa,因为概率总是小于1的,而底数是2,这样取log后会变为负数。费用为负,跑出来的费用就会朝更小走,在这个题上会出问题。那么取个负呢,把负变成正,还是会出问题,取负之后最小就变成了最大,跑出来是最大费用,也是会出问题的。

这时候就应该从反方向进行考虑,求踩坏的最小概率,就是求不踩坏的最大概率,1-p后取log,和以上同理,求出了最大费用。取出来还回去后用1减一下就好了。

新建源点s,汇点t,对于S>B的需要人走,从源点连一条流量为S[i]-B[i],费用为0(出门不需要费用)的边过去,add(s,i,S[i]-B[i],0),对于s<b的,add(i,t,B[i]-S[i],0)。

然后还有一个问题,就是第一次踩的时候,不会触发,那么从原有的边中取一条出来,流量1,费用0就好了。(来源网络,写的炒鸡棒)

然而跑了900多ms,已经想不到让时间降下去的姿势了。。

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1319 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

发表评论

gravatar

快来吐槽一下吧!

  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40