RainAir
My OI Blog
RainAir
「BZOJ 4788」[CERC2016]Bipartite Blanket

题目大意

二分图点有点权,定义点集的权值为点权和,统计二分图中有多少个点集,满足被至少一个匹配覆盖。
$n,m \leq 20$

题解

首先你要知道一个叫做霍尔定理的东西:设 $G$ 中有一组匹配,一端恰好为组成 $X$ 的点的充分必要条件是: $X$ 中的任意 $k$ 个点至少与 $Y$ 中的 $k$ 个点相邻。(摘自百度百科)
这个告诉了我们如何判断一个点集是否能被一个匹配覆盖,但是暴力枚举+模拟时间复杂度不能接受。
所以还有个新科技定理:
如果存在一个匹配覆盖左边的一个点集 $A$, 同时存在一个匹配(不需要和之前的一样)覆盖右边的一个点集$B$。那么就存在一个匹配同时覆盖 $A,B$。
有了这个定理就很好做了。。。这样直接就可以独立处理左右两部分,最后双指针合并了。
现在我们就是要对于一边求出来是否满足霍尔定理中的条件,直接递推一下就好了(如果子集都满足,那么这个点集肯定满足)

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/784
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「BZOJ 4788」[CERC2016]Bipartite Blanket
题目大意 二分图点有点权,定义点集的权值为点权和,统计二分图中有多少个点集,满足被至少一个匹配覆盖。 $n,m \leq 20$ 题解 首先你要知道一个叫做霍尔定理的东西:设 $G$ 中有一组…
扫描二维码继续阅读
2019-08-26
标签
近期评论