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

看了《最小割模型在信息学竞赛中的应用——胡伯涛》的一部分，感觉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的边，所有能到达的点就是答案。

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