CF2097B 快记录 最后更新于 2025-05-01 21:56:47

很深刻的一道图论刻画题。 一开始的想法是 2-SAT，但是因为 2-SAT 计数是 nphard 的，就转化为了 最大独立集问题，但是最大独立集计数不还是 nphard 的吗，而且这两个转化其实是一致的。 不要把问题转化为一个 **具有特殊性质的复杂问题**，而是要把 **具有特殊性质的复杂问题** 转化为 容易的问题。 上面的想法把 决策刻画成了点，边为点的互斥关系（推出关系），其实是浪费了图的 边 的组合意义，永远记住图的定义是 $G(V,E)$，那不如把决策刻画为边，位置刻画为点，这样问题就转化为了边定向问题，是非常容易的。