Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 \leq c \leq 1). One Katu is solvable if one can find each vertex Vi a value Xi (0 \leq Xi \leq 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:…
链接
题解
此题连边十分麻烦，wa了3次….
若给出节点 $a$，$b$，值 $c$ 以及判断方法 $op$，设 $a << 1$ 为 $1$，$a << 1 | 1$ 为 $0$，
- 若 $op$ 为 $&$:当 $c=1$ 时，那么只有 $a$ 与 $b$ 同时为 $1$ 时，$a & b$ 才等于 $1$，并且有且只有当 $a$ 与 $b$ 都为 $1$ 时这个条件才成立，所以 $a$ 与 $b$ 一定要等于 $1$，所以连边 $< a << 1 | 1, a << 1 >$，$< b << 1 | 1,b << 1 >$，表示不管怎么样，$a$ 与 $b$ 的情况都等于 $1$，即：当 $a$ 等于 $0$ 时 $a$ 必等于 $1$，$b$ 等于 $0$ 时 $b$ 必等于 $1$。当 $c=0$ 时，那么当 $a$ 等于 $0$ 时，$b$ 可能为 $0$ 也可以为 $1$，所以是不确定关系，由上面说的一定是确定关系才能连边，所以 $a$ 为 $0$ 的情况就不能连边了；当 $a$ 等于 $1$ 时，$b$ 一定为 $0$ 才能使 $a & b =0$，所以连边：$< a << 1,b << 1 | 1 >$，当然还有$< b << 1,a << 1 | 1 >$。
- 当 $op$ 为 $|$ 时:当 $c=1$ 时，那么当 $a=1$ 时，$b=1$ 或者 $b=0$，所以当 $a=1$ 时出现了两种关系，就是不确定了，就不用连边了；当 $a=0$ 时，那么 $b$ 一定 $=1$,所以是确定关系，连边：$< a << 1 | 1,b << 1 >$，当然还有$< b << 1 | 1,a << 1 >$。当 $c=0$ 时，那么只有当 $a=b=0$ 这个关系，所以这个和上面情况就一样了，即连边$< a << 1,a << 1 | 1 >$,$< b << 1,b << 1 | 1 >$。
- 当 $op$ 为 ^ 时:因为如果 $a=1$,那么 $b$ 必 $=0$；$a=0$，$b$ 必 $=1$；$b=1$，$a$ 必 $=0$；$b=0$，$a$ 必 $=1$。如此看，这四个关系都是确定的，所以都要连边，但是其实我们可以不连，一条边都不用连，因为出a=1的时候一定不会再出现 $a=0$ 了，这四条边是不会产生矛盾的，所以在异或这种情况中只能选择 $a=0$ 或者 $a=1$，所以不会出现矛盾 \cdots \cdots 故不用连边了。
代码
1 |
|
