热闹度(p)子图中最小的度数，尴尬度(q)独立集大小，之间的约束
[ begin{aligned} lfloor n/(p+1)rfloorle q &rightarrow lceil(n-p-1+1)/(p+1)rceille q\ &rightarrow lceil(n-p)/(p+1)rceille q\ &rightarrow (n-p)/(p+1)le q\ &rightarrow n-ple pq+q\ &rightarrow n<(p+1)(q+1) end{aligned} ]
显然(lfloor n/(q+1)rfloorle p)也能推出一样的不等式。
我们每次从图上选出度数最小的点，记录它的度数(d_i)并删除相邻的(d_i)个点，如此反复至无点可选，设进行了(q)次，显然
[ sum_{i=1}^q (d_i+1)=n ]
显然存在一个热闹度(p)是$max d_i $的方案，那么
[ (max d_i+1)qge sum_{i=1}^q(d_i+1)=nrightarrow (max d_i+1)(q+1)>n ]
是满足约束的。
神题啊神题，代码留坑
-
设在点(x)取到(max d_i)，考虑将删除的与(x)相邻的那些点，显然它们的度数(gemax d_i)，故方案就是与 点(x)和(x)相邻的这些点 相邻且未被删除的所有点，热闹度(p=max d_i)。
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/603123.html