最大密度子图
搬论文耳。
需要最大化D=|E|/|V|。其中边、点均可带权。选择的每条边，端点均在子图中。
考虑分数规划。（感觉这一部分的分数规划有趣一些，于是做了笔记）我们用二分来解决这个分数规划问题。
首先二分出了x。如果存在D=|E|/|V|<x，那么说明x还不够优。
根据套路，我们可以得知：
|E|/|V|<x
等价于|E|-x|V|<0。
等价于sigma(ei)-sigma(x*vi)<0
接下来怎么分析？
考虑到最大权闭合子图：
由于我们选择了一条边<u,v>，就必须要选择两个点u与v。于是我们把边视为“另一种点”。这样最大权闭合子图的模型就出来了。
原来的点 对应的点 点权为vi*k。原来的边 对应的点 点权为ei。原来的边 对应的点 向 原来的边的端点 对应的点 连边。
跑最大权闭合子图即可。