先大概移个项 ，就是要你找有没有非空真导出子图满足 \(E-ND\geq 0\)。
如果它只问了 \(E-ND>0\) 这是经典的最大权闭合子图模型，令每条边为左部点，每个点为右部点，边的权值为 \(1\)，点的权值为 \(-D\)，边与对应点连边，如果最终最大权 \(>0\)，则存在这么一个子图。
但是 \(E-ND=0\) 的判断就有点困难，因为原图就是满足这个限制的一个导出子图，如果要排除的话那么需要像计算图的荫度那样枚举必须删掉的点，复杂度起码 \(O(N^2D)\)。
我们重新审视一下这个最大权闭合子图，其还有一个意义：给每条边恰好匹配了一个点，且每个点匹配的边数恰好为 \(D\)。则我们将一条边定向为从其匹配点指向非匹配点，这样的话一个点有恰好 \(D\) 条出边。我们钦定一条边的贡献在匹配点处计算，则一个点至多能提供 \(D\) 的贡献，所以当我们选择一个点在最终的闭合子图内的时候，其出边对应的点都要在闭合子图内，且反过来也是成立的。所以相当于我们要求一个点，满足这个点能走到的点不是全集，只需要强连通分量缩点以后求逆拓扑序最小的 SCC 里面任意选一个点即可。如果全图强连通那么显然找不到。
时间复杂度是 Dicnic 跑二分图匹配的 \(O((ND)^{1.5})\)，不知道这个复杂度为啥要开 \(8\) 秒。submission
标签：一个点,Sparser,ND,复杂度,ARC161F,子图,闭合,Everywhere,匹配 From： https://www.cnblogs.com/275307894a/p/17446703.html