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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!