萌新刚学2-sat求助
查看原帖
萌新刚学2-sat求助
425948
hypnosis楼主2023/5/16 17:23

这道题可以这么连边吗,看题解没有人这么连的。

就是对于同一个党派的两个人,假设一个是 aa 一个是 bb,那么把 aa 和 !b!b 连一个双向边,把 bb 和 !a!a 也连一个双向边,这样就保证同一个党派一定会选一个人。

然后对于敌对的两个人,假设是 xx 和 yy ,那么把 xx 连向 !y!y ,yy 连向 !x!x 。

2023/5/16 17:23
加载中...