2020-2021:teams:legal_string:lgwza:2-sat

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:lgwza:2-sat [2020/08/25 15:59]
lgwza [现实意义]
+++ 2020-2021:teams:legal_string:lgwza:2-sat [2020/08/25 19:21] (当前版本)
lgwza [现实意义]
@@ 行 11: / 行 11: @@
 比如邀请人来吃喜酒，夫妻二人必须去一个，然而某些人之间有矛盾（比如 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$ 个人同时列席？
@@ 行 213: / 行 213: @@
 </code>
 </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.1598342342.txt.gz · 最后更改: 2020/08/25 15:59 由 lgwza