当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [SDOI2019] 热闹又尴尬的聚会

[SDOI2019] 热闹又尴尬的聚会

2019年06月09日  | 移动技术网IT编程  | 我要评论

太仓感知网校,IS拟建恐怖网络,凌豹姿皇上太贪玩

热闹度\(p\)子图中最小的度数，尴尬度\(q\)独立集大小，之间的约束
\[ \begin{aligned} \lfloor n/(p+1)\rfloor\le q &\rightarrow \lceil(n-p-1+1)/(p+1)\rceil\le q\\ &\rightarrow \lceil(n-p)/(p+1)\rceil\le q\\ &\rightarrow (n-p)/(p+1)\le q\\ &\rightarrow n-p\le pq+q\\ &\rightarrow n<(p+1)(q+1) \end{aligned} \]

显然\(\lfloor n/(q+1)\rfloor\le p\)也能推出一样的不等式。

我们每次从图上选出度数最小的点，记录它的度数\(d_i\)并删除相邻的\(d_i\)个点，如此反复至无点可选，设进行了\(q\)次，显然

\[ \sum_{i=1}^q (d_i+1)=n \]

显然存在一个热闹度\(p\)是$\max d_i $的方案，那么
\[ (\max d_i+1)q\ge \sum_{i=1}^q(d_i+1)=n\rightarrow (\max d_i+1)(q+1)>n \]

是满足约束的。

神题啊神题，代码留坑

  1. 设在点\(x\)取到\(\max d_i\)，考虑将删除的与\(x\)相邻的那些点，显然它们的度数\(\ge\max d_i\)，故方案就是与 点\(x\)和\(x\)相邻的这些点 相邻且未被删除的所有点，热闹度\(p=\max d_i\)。

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网