标签: 2-SAT

1 篇文章

洛谷 – P4171 – [JSOI2010]满汉全席
题目给定 $n$ 种食材,对于每种食材,有两种制作方法。对于每一种食材,只能用一次,也就是必须恰好选择一种制作方法。一道菜品的信息,同时包括食材和制作方法。
题目给定了 $m$ 条限制,每条限制包含两个菜品的信息。对于每条限制,限制被满足,当且仅当:在给出的两个菜品中,至少有一个菜品被制作出来。
问:是否存在一种菜品制作方法,使得每条限制都被满足?