Java教程

2022.4

本文主要是介绍2022.4，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

四月了啊...

4.1

T1

不算太难，不写了

T2

给你一个 \(n\) 个点的无向图，计数满足 \(K\) 个限制的生成树数量，每个限制是一个点集 \(S_i\)，要求 \(S_i\) 在生成树上的导出子图联通。

\(n\leq 500,K\leq 2000\)。

生成树计数肯定是矩阵树定理。

考虑每一个限制 \(S_i\)，\(S_i\) 的导出子图的边数 \(cnt_i\leq |S_i|-1\)，且该限制被满足当且仅当取到等号。

我们考虑给原图每条边 \((i,j)\) 赋上边权 \(w(i,j)\)，\(w(i,j)\) 为同时包含 \(i\) 和 \(j\) 的限制个数，我们发现这样，对于它的生成树 \(T\)，边权和 \(w(T)=\sum cnt_i\leq\sum(|S_i|-1)\)，等号取到当且仅当所有限制都被满足，所以满足条件的生成树就是最大生成树。

最大生成树就是经典做法了，忘了的话去看一眼 Luogu P4208 [JSOI2008]最小生成树计数。

还有 \(w(i,j)\) 的计算用 bitset 优化一下就是 \(O(\dfrac{n^2K}{\omega})\)。

总复杂度 \(O(n^3+\dfrac{n^2K}{\omega})\)。

T3

明天补

这篇关于2022.4的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航