2020-2021:teams:legal_string:lgwza:2-sat
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:lgwza:2-sat [2020/08/25 16:07] lgwza [例题] |
2020-2021:teams:legal_string:lgwza:2-sat [2020/08/25 19:21] (当前版本) lgwza [现实意义] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 比如邀请人来吃喜酒，夫妻二人必须去一个，然而某些人之间有矛盾（比如 A 先生与 B 女士有矛盾，C 女士不想和 D 先生在一起），那么我们要确定能否避免来人之间没有矛盾，有时需要方案。这是一类生活中常见的问题。 | 比如邀请人来吃喜酒，夫妻二人必须去一个，然而某些人之间有矛盾（比如 A 先生与 B 女士有矛盾，C 女士不想和 D 先生在一起），那么我们要确定能否避免来人之间没有矛盾，有时需要方案。这是一类生活中常见的问题。 | ||
| - | 使用布尔方程表示上述问题。设 $a$ 表示 $A$ 先生去参加，那么 $B$ 女士就不能参加 $(\neg a);b$ 表示 $C$ 女士参加，那么 $\neg b$ 也一定成立（D 先生不参加）。总结一下，即 $(a \or b)$（变量 $a,b$ 至少满足一个）。对这些变量关系建有向图，则有：$ab ba $（$a$ 不成立则 $b$ 一定成立；同理，$b$ 不成立则 $a$ 一定成立）。建图之后，我们就可以使用缩点算法来求解 2-SAT 问题了。 | + | 使用布尔方程表示上述问题。设 $a$ 表示 $A$ 先生去参加，那么 $B$ 女士就不能参加 $(\neg a);b$ 表示 $C$ 女士参加，那么 $\neg b$ 也一定成立（D 先生不参加）。总结一下，即 $(a \vee b)$（变量 $a,b$ 至少满足一个）。对这些变量关系建有向图，则有：$\neg a\Rightarrow b\ \wedge \neg b\Rightarrow a $（$a$ 不成立则 $b$ 一定成立；同理，$b$ 不成立则 $a$ 一定成立）。建图之后，我们就可以使用缩点算法来求解 2-SAT 问题了。 |
| ===== 常用解决方法 ===== | ===== 常用解决方法 ===== | ||
| 行 29: | 行 29: | ||
| ===== 例题 ===== | ===== 例题 ===== | ||
| - | **HDU 3062** [[http://acm.hdu.edu.cn/showproblem.php?pid=3062|**Party**]] | + | **HDU 3062 [[http://acm.hdu.edu.cn/showproblem.php?pid=3062|Party]]** |
| > 题面：有 $n$ 对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有 $1$ 人可以列席。在 $2n$ 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的 $2$ 个人是不会同时出现在聚会上的。有没有可能会有 $n$ 个人同时列席？ | > 题面：有 $n$ 对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有 $1$ 人可以列席。在 $2n$ 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的 $2$ 个人是不会同时出现在聚会上的。有没有可能会有 $n$ 个人同时列席？ | ||
| 行 214: | 行 214: | ||
| </hidden> | </hidden> | ||
| + | ===== 练习题 ===== | ||
| + | HDU1814 [[http://acm.hdu.edu.cn/showproblem.php?pid=1814|和平委员会]] | ||
| + | |||
| + | POJ3683 [[http://poj.org/problem?id=3683|牧师忙碌日]] | ||
| + | |||
| + | ===== 参考链接 ===== | ||
| + | |||
| + | [[https://oi-wiki.org/graph/2-sat/|OI Wiki]] | ||
2020-2021/teams/legal_string/lgwza/2-sat.1598342849.txt.gz · 最后更改: 2020/08/25 16:07 由 lgwza
