这道题能用 2-SAT 做吗

P1285 队员分组

Pwtking @ 2023-05-23 16:43:48

rt，理论上貌似 2-SAT 可做：若两个人不互相认识，那么一定存在其中一个人在 a 组，另一个人在 b 组，连边即可。

by LoserKugua @ 2023-05-23 16:59:35

理论上来说这种判二分图都可以上2-SAT(大概除了在线判定都可以?)，不过感觉没啥必要

by LoserKugua @ 2023-05-23 17:05:51

正好2-SAT给出一组可行解也可以解决此问题

by Pwtking @ 2023-05-23 18:55:51

@woshilaji_ OK谢谢

by Pwtking @ 2023-05-23 20:36:27

补充：题目若不加 “使两组人数之差尽量小” 即可用 2-SAT 求解，但是题目加了，而 2-SAT不能控制两组之差，所以 2-SAT HACKed。

by Pwtking @ 2023-05-23 20:37:39

用了2-SAT的后果

by LoserKugua @ 2023-05-24 10:27:00

@Tsinghua_pwtking 用2-SAT划分组之后01背包dp好像也没啥问题吧...

by Pwtking @ 2023-05-24 12:29:24

@woshilaji_ 理论上貌似可行，但我太懒（逃

|