【算法】带花树 —Qiuly

刚了解很不熟练,有问题请及时指出 QAQ 带花树 带花树通常用于解决一般图最大匹配问题。 至于一般图最大权匹配问题,毒瘤请移步这里。 考虑如何处理奇环,让环上的点两两匹配,总会剩下一个点,而且每一个环上的点都存在一种环上匹配方案使得该点被剩下,那么考虑将环缩成点,缩完的点一样可以匹配。 如果要支持输 阅读更多…

【题解】Everything on It 容斥 ARC096C —Qiuly

题意: 给你 $n$ 种酱。 你需要若干碗拉面,并且满足: 你可以在每碗拉面上放若干酱,也可以不放,容易发现方案数为 $O(2^n)$ 。 不能出现放的酱一样的两碗甚至更多拉面。 每一种酱至少在两碗拉面中加了。 求拉面集合的方案数。 考虑容斥,设 $S(i)$ 表示有 $i$ 个不合法的酱,其他的 阅读更多…