关于2-SAT(2-Satisfiability)资料的话就是伍昱的《由对称性解2-SAT问题》PPT和赵爽的《2-SAT 解法浅析》PDF。
简要意思就是给定N个组（每个组2个元素）、M个互斥关系，从每个组里挑1个使得给定的不满足任何互斥关系。
但是解决这类问题的关键还是在于建模，基本建模就是对于两个不相容的点i、j，构图方式为：i->j'(i和j冲突，选i只能选j')和j->i'（i和j冲突，选j只能选i'）。
解2-SAT方法是，对原图求一次强连通分量，然后看每组中的两个点是否属于同一个强连通分量，如果存在这种情况，那么无解。
下面是我做过的几道2SAT问题，持续更新。
[HDU3622]Bomb Game
其 实如果知道什么是2-SAT的话这题就变得很裸了。用2*i表示i组的第一个炸弹，2*i+1表示i组的第二个炸弹，然后二分最大半径r，每个组里选一个 炸弹，对于不同组的两个炸弹i和炸弹j只要有dis[i][j] <= 2*r的话那么炸弹i就与炸弹j冲突，连边i->j^1和j->i^1再验证2-SAT即可。
bool check(double r)//对于两个不相容的点i,j 构图方式为：i->j'和j->i' { init(); for (int i = 0;i < 2*n; i++) for (int j=i+1;j < 2*n;j++) { if ((i>>1) != (j>>1) && dis[i][j] <= r*2)
{ addedge(i,j^1); addedge(j,i^1); } } return TwoSat(); }
[SRM 464 DIV1 500]ColorfulDecoration
跟上题几乎一模一样，只不过变成正方形，二分边长s， 验证|x1 - x2| ≥ s or |y1 - y2| ≥ s。
[POI2001]Peaceful Commission [POI2001]和平委员会
一样的两题，不过我的某个代码只能过一个，不知道是那个数据有问题，这个就是PPT上的例题，不仅要验证2-SAT，还要输出一个方案，输出方案具体的参见PDF。
[PKU3207]Ikki's Story IV - Panda's Trick
题意：平面上有一个圆，圆的边上按顺时针放着0..n-1共n个点。现在要连m条边，比如a，b，那么a到b可以从圆的内部连接，也可以从圆的外部连接。给你的信息中，每个点最多只能连一条边。问是否可以连接这m条边，使这些边都不相交。
对 于每条边有两个选择：内部或者外部，而且边与边之间有关系，于是2-SAT，把一条边拆成2个点，2*i表示i边放在内部，2*i+1表示i边放在外部， 当边i与边j冲突时建立2*i<->2*j+1、2*j<->2*i+1，验证2-SAT即可。
inline bool conflict(int i,int j) { bool flag = 0; flag |= ((x[j] > x[i] && x[j] < y[i]) && !(y[j] > x[i] && y[j] < y[i])); flag |= ((y[j] > x[i] && y[j] < y[i]) && !(x[j] > x[i] && x[j] < y[i])); return flag; } void build()//对于两个不相容的点i,j 构图方式为：i->j'和j->i' { init(); for (int i = 0;i < n;i++) for (int j = i+1;j < n;j++) { if (conflict(i,j)) { addedge(2*i,2*j+1); addedge(2*j+1,2*i); addedge(2*j,2*i+1); addedge(2*i+1,2*j); } } }
[PKU2296]Map Labeler
题意：给定n个点，在这n个点上方或者下方可以放一个平行x、y轴的矩形（点在矩形的边的中点），问能放完n个矩形（不相交）的最大边长是多少。
首 先是二分答案，然后是比较麻烦的构图，要分好几种情况讨论，先设2*i:矩形放点i上面 2*i+1:矩形放点i下面，那么首先当abs(x[i]-x[j]) >= r时必定是可以任意放的。而当abs(x[i]-x[j]) < r时：①abs(y[i]-y[j]) < r：当y[i] == y[j]时两个点的矩形可以一上一下，否则只能是上面的点的矩形放上面，下面的点的矩形放下面。②abs(y[i]-y[j]) < 2*r：除了上面的点的矩形放下面，下面的点的矩形放上面的情况都是可以的，按此构图即可。
bool check(int r)//对于两个不相容的点i,j 构图方式为：i->j'和j->i' { init(); //2*i:矩形放点i上面 2*i+1:矩形放点i下面 for (int i = 0;i < n; i++) for (int j = i+1;j < n;j++) { if(abs(x[i]-x[j]) < r) { if (abs(y[i]-y[j]) < r) { if (y[i] == y[j]) { addedge(2*i+1,2*j); addedge(2*j,2*i+1); addedge(2*j+1,2*i); addedge(2*i,2*j+1); } else if (y[i] > y[j]) { addedge(2*i,2*i+1); addedge(2*j+1,2*j); } else { addedge(2*j,2*j+1); addedge(2*i+1,2*i); } } else if (abs(y[i]-y[j]) < 2*r) { if (y[i] > y[j]) { addedge(2*i,2*j); addedge(2*j+1,2*i+1); } else { addedge(2*j,2*i); addedge(2*i+1,2*j+1); } } } } return TwoSat(); }
[PKU3648]Wedding
这个题较麻烦，题意是
“n-1对夫 妇去参加一对新人的婚礼。人们坐在一个很长很长的桌子的两侧（面对面）。新郎新娘在桌子一头面对面座。新娘不希望看见她对面的一排有一对夫妇坐着（所有夫 妇需要分开两排座）。同时，一些人之间有暧昧关系，新娘也不希望有暧昧关系的人同时坐在她对面的一排（但是可以同时和她并排）。问能否满足新娘的要求，可 以的话，输出一种方案。”
首先这题蕴含很多冲突关系，这 时我们就应该要向2-SAT的方面思考下了。首先，每个人都可以坐在桌子的左右两边。那么我们把每个人拆成两个点，坐左边用i表示，坐右边的用i'表示。 然后再定义第i对夫妇的2*i表示女的，2*i+1表示男的。那么i' = i + 2*n。也就是2*i:女左 2*i+1:男左 2*i+2*n:女右 2*i+1+2*n:男右。
因为有暧昧关系的人可以跟新娘坐一排那么我们让新娘坐左边（左右一样），为了防止有新娘左右边的解出现我们初始化：
addedge(2*0+2*n,2*0);(如果新娘坐右边我们就必须同时让新娘坐左边，显然是矛盾的，故加了这句后新娘永远也不会坐到右边了)。
addedge(2*0+1,2*0+1+2*n);(同理新郎坐右边)。
对于所有的夫妇有：选男左就得选女右，选女左就得选男右，选男右就得选女左，选女右就得选男左。
for (int i = 0;i < n;i++) { addedge(2*i,2*i+1+2*n); addedge(2*i+1,2*i+2*n); addedge(2*i+2*n,2*i+1); addedge(2*i+1+2*n,2*i); }
对于m个暧昧关系有：选了男右的就不能选女右，选了女右就不能选男右。
for (int i = 0;i < m;i++) { scanf("%d%c%d%c",&x,&c1,&y,&c2); x = 2*x + (c1 == 'h'); y = 2*y + (c2 == 'h'); addedge(x+2*n,y); addedge(y+2*n,x); }
最后验证2-SAT再求出一个解就好了~。
[PKU3678]Katu Puzzle
题意：一些点，点的取值可以是0或者1，一些边，有权值，有运算方式（AND，OR，XOR），要求和这条边相连的两个点经过边上的运算后的结果是边的权值。问是否能把每个点赋值以满足所有边的要求。
这题每个点有两个选择：0或1，所以二选一，并且点与点之间又有限制关系，于是可以2-SAT。
每个点拆成2个：2*i表示i号点放0，2*i+1表示i号点放1，那么根据逻辑关系即可构图。
void build()//对于两个不相容的点i,j 构图方式为：i->j'和j->i' { init(); int x,y,z; char s[5]; for (int i = 0;i < m;i++) { scanf("%d%d%d%s",&x,&y,&z,s); //2*x:x位置放0 2*x+1:x位置放1 if (strcmp(s,"AND") == 0) { if (z == 1) { addedge(2*x,2*x+1); addedge(2*y,2*y+1); addedge(2*x+1,2*y+1); addedge(2*y+1,2*x+1); } else { addedge(2*x+1,2*y); addedge(2*y+1,2*x); } } if (strcmp(s,"OR") == 0) { if (z == 1) { addedge(2*x,2*y+1); addedge(2*y,2*x+1); } else { addedge(2*x,2*y); addedge(2*y,2*x); addedge(2*x+1,2*x); addedge(2*y+1,2*y); } } if (strcmp(s,"XOR") == 0) { if (z == 1) { addedge(2*x+1,2*y); addedge(2*y,2*x+1); addedge(2*y+1,2*x); addedge(2*x,2*y+1); } else { addedge(2*x+1,2*y+1); addedge(2*y+1,2*x+1); addedge(2*x,2*y); addedge(2*y,2*x); } } } }
[PKU3683]Priest John's Busiest Day
题意：有 n个婚礼，每个婚礼有起始时间Si，结束时间Ti，还有一个主持时间ti，ti必须安排在婚礼的开始或者结束，主持由祭祀来做，但是只有一个祭祀，所以各 个婚礼的主持时间不能重复，问你有没有可能正常的安排主持时间，不能输出no，能的话输出任意一个满足的方案，即每个婚礼的主持时间段。
这题因为限制了首做或者尾做，二选一，于是就很显然要2-SAT了，把每个Si,Ti看成一组，冲突就是对于不同的组i,j，分别考虑头尾是否冲突并连边即可。
void build()//对于两个不相容的点i,j 构图方式为：i->j'和j->i' { init(); int x,y,z; char s[5]; for (int i = 0;i < m;i++) { scanf("%d%d%d%s",&x,&y,&z,s); //2*x:x位置放0 2*x+1:x位置放1 if (strcmp(s,"AND") == 0) { if (z == 1) { addedge(2*x,2*x+1); addedge(2*y,2*y+1); addedge(2*x+1,2*y+1); addedge(2*y+1,2*x+1); } else { addedge(2*x+1,2*y); addedge(2*y+1,2*x); } } if (strcmp(s,"OR") == 0) { if (z == 1) { addedge(2*x,2*y+1); addedge(2*y,2*x+1); } else { addedge(2*x,2*y); addedge(2*y,2*x); addedge(2*x+1,2*x); addedge(2*y+1,2*y); } } if (strcmp(s,"XOR") == 0) { if (z == 1) { addedge(2*x+1,2*y); addedge(2*y,2*x+1); addedge(2*y+1,2*x); addedge(2*x,2*y+1); } else { addedge(2*x+1,2*y+1); addedge(2*y+1,2*x+1); addedge(2*x,2*y); addedge(2*y,2*x); } } } }