社区讨论
2-SAT 一个震惊的问题
学术版参与者 7已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @mc5prax3
- 此快照首次捕获于
- 2025/06/21 12:03 8 个月前
- 此快照最后确认于
- 2025/11/04 07:03 4 个月前

其中 和 表示这个 的两种状态。
这是显然有解的,没有 和 在同一强联通分量里。由于我们选 scc 小者,解应为 ,,,。
但是问题就在这里,如果我们选了 就应该选 ,选了 就应该选 ,选了 就应该选 ,这不就矛盾了?!
我不知道真实情况中会不会出现这种图的存在情况,但我认为如果出现这种情况的话,岂不是 2-SAT 就崩塌了?
回复
共 10 条回复,欢迎继续交流。
正在加载回复...