关于 2-sat
  • 板块学术版
  • 楼主BYR_KKK
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/19 10:13
  • 上次更新2024/6/19 16:44:29
查看原帖
关于 2-sat
802664
BYR_KKK楼主2024/6/19 10:13

证明正确性时发现有解情况下 x 和 -x 在缩完点的 DAG 上不存在 x -> -x 或 -x -> x 的路径,请问这是对的吗?

理由大概就是 2-sat 的图是对称的,如果 x -> -x 则必然可以通过对称得到 -x -> x,与有解矛盾。

2024/6/19 10:13
加载中...