以后推半天性质还是很模糊的话，也尝试尝试直接套算法。。
算法导向！2-SAT！
强行 2-SAT 的话，我们会有以下约束：
- 若一个嫌疑人的供词中存在一个假话，他必然是犯人。
- 若一个嫌疑人的供词中存在一个假话，其它话必然是真的。
- 若一个嫌疑人不是犯人，他说的所有话一定都是真的。
此时暴力连边图的规模是 \(O(m^2)\) 的。考虑优化第二个约束。
把【其它话】套路地拆成前后缀，优化建图即可。具体而言：
- 若第 \(i\) 条供词是假的，则前 \(i-1\) 条和后若干条都是真的，前 \(i\) 条和后对应条是假的。
- 若前/后 \(i\) 条是真的，则前/后 \(i-1\) 条也是真的，第 \(i\) 条也是真的。
- 若前/后 \(i\) 条是假的，则前/后 \(i+1\) 条也是假的。
为了建图方便，不妨把证词的正确性也拆成两个点，此时设第 \(i\) 个嫌疑人一共有 \(k\) 条证词，我们会对其证词开 \(6k\) 个点，分别表示前缀/后缀/第 \(i\) 证词是否正确。
标签：条和后,嫌疑人,证词,寻找,条是,罪犯,真的,供词,UER From： https://www.cnblogs.com/ydtz/p/17762690.html