1. 首页
  2. 网络流

HDU 3251 Being a Hero (最小割)

题目链接:点我~~

题意:n个点m条边的有向图,f个可选城市,每个城市都有其价值w,国王的城市在1,要分配一些城市,分配的原则是:只能在规定的f个城市中选若干个,这f个城市每个都有一个价值,被选择的城市要与城市1隔离,所以需要花费一些费用来破坏边。问能获取到的最大利益,以及要破坏的边。

思路:求能获取的最大利益,先建立一个超级汇点,将f个可选城市与汇点连接,价值为权值,f个城市的价值总和减去跑出的最小割即为可获得的最大价值,过程肯定优先选取价值低的边来破坏。在残留网络中,从源点遍历所有能走到的点,即属于S集,其余的为T集,如果一条边连接着S集的点与T集的点,说明该边一定为割边。

 

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

发表评论

gravatar

快来吐槽一下吧!

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