频道栏目
IT货架 > > 正文
POJ3155HardLife(最大密度子图)
网友分享于:Jun 12, 2018 11:44:31 PM    来源: IT货架   

裸题。输入一个无向图,输出最大密度子图(输出子图结点数和升序编号)。

看了《最小割模型在信息学竞赛中的应用——胡伯涛》的一部分,感觉01分数规划问题又是个大坑。暂时还看不懂。

参考http://blog.csdn.net/power721/article/details/6781518

 

构图:

把原图中的无向边转换成两条有向边,容量为1

设一源点,连接所有点,容量为U(取m)。

设一汇点,所有点连接汇点,容量为 U+2g-dv 

二分枚举最大密度g,其中dvv的度。

判断(U*n-MaxFlow)/2.>=0

最后跳出的L就是最大密度。

拿这个L再重新建图,求最大流。

然后从s出发bfs或者dfs,走残留容量大于0的边,所有能到达的点就是答案。

具体分析过程见胡伯涛的论文《最小割模型在信息学竞赛中的应用》

 

 


广告服务联系QQ:1134687142 | 网站地图

版权所有: IT货架- 内容来自互联网,仅供用于技术学习,请遵循相关法律法规. 京ICP备11030978号-1