强连通分量

求法

Tarjan 和 Kosaraju 算法

Tarjan

维护low值注意:

例题

双联通分量

割点和桥

边双连通分量和点双连通分量

求法

例题

[USACO]Redundant Paths

二分图

完美匹配

若一个匹配中图中每个顶点都和匹配中的某条边关联则称之为完美匹配。

Hall定理

二分图$G=(V,E)$,其中$V$划分为$A,B$,$C$是$A$的子集且$\left|C\right|=k$。

存在一个匹配M使得$C$中每个点都存在于匹配中(存在C的完美匹配),当且仅当$1\le i\le k$,$C$中任意i个点都至少和$B$中i个点相连。

点覆盖

选出一个点集使得对于任意一条边都至少与一个黑点相连。

独立集

例题

2-SAT

SAT是指给出一些条件(元素根据逻辑运算的结果),问是否存在合法方案使得满足所有条件。

SAT 是适定性(Satisfiability)问题的简称。一般形式为 k - 适定性问题,简称 $k-SAT$。而当$k\ge2$时该问题为 NP 完全的。所以我们只研究$k=2$的情况。

例题

[NOI2017]游戏

对于x的情况,观察到最多只有8个x,所以可以枚举地图为x的场次选择情况。

但这样复杂度乘上$O(3^n)$,只有95分。

转换思路枚举没选哪个,只需枚举前两个即可涵盖所有情况(不选1=选2/3,不选2=选1/3,选1/2/3都枚举到了)。这样复杂度降为$O(2^n)$。

综合例题

[BZOJ1135|POI2009]Lyz

根据Hall定理进行判定。

由Hall定理,设$a_i$表示选择i号鞋的人数,只要每个区间$[l,r]$满足$$\sum\limits_{i=l}^ra_i\le(r+d-l+1)\cdot k$$即足够(有可行匹配方案)。

变形得$$\sum\limits_{i=l}^r(a_i-k)\le k\cdot d$$

于是变为了最大子段和问题,线段树维护即可。

[BZOJ2725]故乡的梦

keyboard_arrow_up