Posts tagged with 2-SAT


题解 2-SAT 一眼题,但是很遗憾,我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解,我个人以为,只要染色数量等于点数就是可行解。有哪里不对的么?? 但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。 传送门 题意 有n个人手中有n张卡,每个人说两句话,有一句必定为真,有一句必定为假。说了2-sat一眼题…… 两句话分别说,我自己手上是几号卡,别人手上是几号卡,保证不存在相同的陈述。 思路: 对于每两个人 i 和…

11.HDU 1814 Peaceful Commission 题意: 建图老题意,表示有n对人要出席一个会议,但是有m个恶劣的关系不允许同时出现。 但是不一样的地方就是需要输出可行解的最小序列 思路: 让你判断一下还是很简单的,但是输出最小序列真的让博主感到很无力,想了很长时间也没有一个快速的方法。看了题解是说暴搜索可解,我这里說一下暴搜思路。 先将所有节点染成白色(初始化),再进行遍历。如果已经染成红色或者黑色的节点就跳过,否则,我们先尝试将第一个节点染成红色,再进行暴力dfs缩点,暴力过程中,优先让第一个节点染成红色,…

6. POJ 2296 Map Labeler 题意: 平面区域内部有n个点,以这个点为上底边中心或者下底边中心作正方形,要求使所有正方形都不相交,问正方形最大的边长为多少。 思路: 和炸弹那道题差不多,二分区间,判断即可。 令( Dis_x [a][b] = \left| x[a] – x[b] \right|…

附带我的学习来源,这里包含以上所有题目的题解和代码。实在想不出来我就是看这里的。 1. HDU 3062 Party 题意: 有n对夫妻被邀请参加一个聚会,因为场地的问题,每对夫妻中只有1人可以列席。在2n 个人中,某些人之间有着很大的矛盾(当然夫妻之间是没有矛盾的),有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席? (中文题面就复制粘贴一下了……) 思路: 非常典型的 2-sat 模型,如果两对夫妻 A…