Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

有N个变量,每个变量都能取T或F,需要满足M个条件: X_{i} = T or X_{j} = F

要给每个变量赋值,满足所有条件.

构造有向图G,每个X_{i}拆成两个点2i和2i+1, 分别表示X_{i}取T或者F. 每个变量选其中的一个进行标记,标记了节点2i表示X_{i}=T,标记2i+1表示X_{i}=F.

对于每个条件,如X_{i} = T or X_{j} = F,可以从表示点i为F的节点到表示点j为F的节点连一条边,表示如果点i为F,那么点j一定是F. 同时,还要从表示点j为T的点向表示点i为T的点连一条边.

DFS方法




Blog content follows the [Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en)
本站总访问量为 访客数为
Use Volantis as theme