2012-0014

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

占 by大肥羊～ 明天D组比完赛再写，现在想写的童鞋可以抢走 ^_^


这题是标准的2-SAT问题模型

2-SAT问题，简单的说就是有n个组，每组里面有两个不同的元素，现在每个组都必须选其中一个元素出来，并且满足一些两两约束条件，比如某两个元素不能同时出现，元素i出现则元素j必须出现等

2-SAT模型有很多现成的模板，但是不管什么模板，都需要自己手动建边来表示约束条件

2-SAT算法在做的时候需要把每个点拆成两个点，i拆成i和i',i表示选这个元素，i'表示不选这个元素，所以n组的话一共要4*n的数组空间来存点，前面2*n的空间表示每组的第一个元素，后面2*n的空间表示每组的第二个元素，比如i表示第i组选第一个元素，i+n表示第i组不选第一个元素，i+2n表示第i组选第二个元素，i+3n表示第i组不选第二个元素

对应到本题中，首先二分气球的半径

然后对于每组气球i，首先只能选其中一个气球，即在i和i+3n之间建边，表示选第一个元素就不能选第二个元素，在i+n和i+2n之间建边表示选第二个元素就不能选第一个元素

然后再根据两组气球之间的距离继续建边，比如选第i组的红色气球就不能选第j组的蓝色气球之类的，每个条件都建相应的边

然后就是模板了

占 by大肥羊～ 明天D组比完赛再写，现在想写的童鞋可以抢走 ^_

这题是标准的2-SAT问题模型

2-SAT问题，简单的说就是有n个组，每组里面有两个不同的元素，现在每个组都必须选其中一个元素出来，并且满足一些两两约束条件，比如某两个元素不能同时出现，元素i出现则元素j必须出现等

2-SAT模型有很多现成的模板，但是不管什么模板，都需要自己手动建边来表示约束条件

2-SAT算法在做的时候需要把每个点拆成两个点，i拆成i和i',i表示选这个元素，i'表示不选这个元素，所以n组的话一共要4*n的数组空间来存点，前面2*n的空间表示每组的第一个元素，后面2*n的空间表示每组的第二个元素，比如i表示第i组选第一个元素，i+n表示第i组不选第一个元素，i+2n表示第i组选第二个元素，i+3n表示第i组不选第二个元素

对应到本题中，首先二分气球的半径

然后对于每组气球i，首先只能选其中一个气球，即在i和i+3n之间建边，表示选第一个元素就不能选第二个元素，在i+n和i+2n之间建边表示选第二个元素就不能选第一个元素

然后再根据两组气球之间的距离继续建边，比如选第i组的红色气球就不能选第j组的蓝色气球之类的，每个条件都建相应的边

然后就是模板了