裸题。输入一个无向图,输出最大密度子图(输出子图结点数和升序编号)。
看了《最小割模型在信息学竞赛中的应用——胡伯涛》的一部分,感觉01分数规划问题又是个大坑。暂时还看不懂。
参考http://blog.csdn.net/power721/article/details/6781518
构图:
把原图中的无向边转换成两条有向边,容量为1。
设一源点,连接所有点,容量为U(取m)。
设一汇点,所有点连接汇点,容量为 U+2g-dv 。
二分枚举最大密度g,其中dv为v的度。
判断(U*n-MaxFlow)/2.>=0。
最后跳出的L就是最大密度。
拿这个L再重新建图,求最大流。
然后从s出发bfs或者dfs,走残留容量大于0的边,所有能到达的点就是答案。
具体分析过程见胡伯涛的论文《最小割模型在信息学竞赛中的应用》
版权所有: IT货架- 内容来自互联网,仅供用于技术学习,请遵循相关法律法规. 京ICP备11030978号-1