题解 2-SAT 一眼题，但是很遗憾，我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解，我个人以为，只要染色数量等于点数就是可行解。有哪里不对的么？？ 但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。 传送门 题意 有n个人手中有n张卡，每个人说两句话，有一句必定为真，有一句必定为假。说了2-sat一眼题…… 两句话分别说，我自己手上是几号卡，别人手上是几号卡，保证不存在相同的陈述。 思路： 对于每两个人 i 和 j 的陈述，进行判断，如果产生矛盾，则建边。 产生矛盾是指两个的陈述，主语或者谓语有一个不同就产生了矛盾。 eg 1 号 手中有 2 号卡 < —- > 1 号手中有 3 号卡 1 号 手中有 2 号卡 < —- > 2…
11.HDU 1814 Peaceful Commission
题意：
建图老题意，表示有n对人要出席一个会议，但是有m个恶劣的关系不允许同时出现。
但是不一样的地方就是需要输出可行解的最小序列
思路：
让你判断一下还是很简单的，但是输出最小序列真的让博主感到很无力，想了很长时间也没有一个快速的方法。看了题解是说暴搜索可解，我这里說一下暴搜思路。
先将所有节点染成白色（初始化），再进行遍历。如果已经染成红色或者黑色的节点就跳过，否则，我们先尝试将第一个节点染成红色，再进行暴力dfs缩点，暴力过程中，优先让第一个节点染成红色，第二个染成黑色。如果没有任何冲突，则表示缩点成功。否则尝试将第二个节点染成红色，再缩点，如果还不行，就说明无解了。
#include
6. POJ 2296 Map Labeler 题意： 平面区域内部有n个点，以这个点为上底边中心或者下底边中心作正方形，要求使所有正方形都不相交，问正方形最大的边长为多少。 思路： 和炸弹那道题差不多，二分区间，判断即可。 令( Dis_x [a][b] = \left| x[a] – x[b] \right| , Dis_y [a][b] = \left| y[a] – y[b] \right| )，边长为 mid，设 a 表示 a 矩阵放上面，~a 表示 a 矩阵放下面。 建图： * (Dis_x[a]…
附带我的学习来源，这里包含以上所有题目的题解和代码。实在想不出来我就是看这里的。
1. HDU 3062 Party
题意：
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？ （中文题面就复制粘贴一下了……）
思路：
非常典型的 2-sat 模型，如果两对夫妻 A B ，丈夫A0 与 妻子B1 有仇，那么就建 A0 -> B0 , A1 -> B1 两条边。
#include