tkdsheep-solution-0014

从 Trac 迁移的文章

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

原文章内容如下：

{{{
这题是标准的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组的蓝色气球之类的，每个条件都建相应的边

然后就是模板了，不过好像zju模板上没找到，我是比赛的时候外网随便搜了一段代码，把他的建图改了一下交的
}}}

这题是标准的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组的蓝色气球之类的，每个条件都建相应的边
然后就是模板了，不过好像zju模板上没找到，我是比赛的时候外网随便搜了一段代码，把他的建图改了一下交的