• 给定图，最大化 $d=\frac{|E'|}{|V'|}$
• 二分答案，转为判定性问题，最大化 $|E'|-d|V'|$，并判定上式是否大于等于 $0$
• 显然如果选了一条边，它的两个端点就必须选
• 点有 $d$ 的负权，边有 $1$ 的正权，转化为最大权闭合子图模型，时间复杂度 $O(\log n\times{网络流复杂度\propto(n+m)})$

以下纯属放屁

• 但是这样做复杂度就跟 $n+m$ 相关了，非常劣啊！
• 怎么让它只跟 $n$ 相关呢？
• 注意到，如果选了一个点集，那么选的边集一定是导出子图
• 那么 $|E'|=\frac{1}{2} (\sum r_{u}-c)$ 其中 $c$ 的含义是满足两个点中有且仅有一个在被选点集里的点对数
• 我们依然要最大化 $|E'|-|V'|$，由于我们不喜欢分数，所以以下都 $\times 2$，考虑选一个点的贡献
• 点权为：$r_{u}-2d$，按照形如最大权闭合子图模型的套路建图，然后直接相连的两个点互相连边权为 $1$ 的边 以上纯属放屁

• 考虑二分边界：考虑任意两个子图密度的差值的最小值，其实就是 $O\left( \frac{1}{n^2} \right)$