学习笔记 - 2sat

决定重新启用Markdown……只是因为它支持MathJax数学公式
noip考完&＃xff0c;既轻松又无奈&＃xff0c;回来慢慢填坑
这篇博客也是拖了好久&＃xff0c;通过kuangbin的博客才弄懂2-sat的

---

2-sat问题

先说sat问题——指一种每个变量只有两个值&＃xff08;true or false&＃xff09;&＃xff0c;并且给出一些限制&＃xff0c;每个限制的基本形式为&＃xff1a;

\(a\ XOR/OR/AND\ b\ XOR/OR/AND\ c\ (etc.) &＃61; true\)

另外当每个限制涉及的变量只有两个时&＃xff0c;这类问题称为2-sat问题&＃xff0c;即 \(a\ XOR/OR/AND\ b&＃61;true\)&＃xff0c;当然也可以限制值为 false&＃xff0c;在这里a,b也可以不保证不同。求这样的问题的解&＃xff0c;即每一个变量选或不选。

2-sat问题的建模

假设现在有N个变量形成2-sat问题。

由于一个变量要么为true&＃xff0c;要么为false&＃xff1b;我们可以把变量拆分成两个点——一个点表示true&＃xff0c;另一个表示false&＃xff0c;这样一来我们有 2N 个点&＃xff0c;也就是 N 个点对&＃xff1b;下面我们称 A、A&＃39; 分别表示变量A选、不选。然后我们称“一个变量的状态”为“这个状态所对应的点选或不选”。

我们可以将点连边&＃xff0c;边(X,Y)表示选X就必须选Y&＃xff1b;下面举两种最基本的例子&＃xff1a;

①选变量A就必须选变量B&＃xff0c;则连 (A,B) (B&＃39;,A) 两条有向边&＃xff1b;
②必须选变量A&＃xff0c;则连 (A&＃39;,A) 的有向边&＃xff1b;

1-可行性问题求解

即判断某一方案是否可行。常用于检验二分答案。

通过求强连通分量求解——如果 点v 和 点v&＃39; 同时存在于一个强连通分量中&＃xff0c;则说明从“选 变量v” 这一起点出发&＃xff0c;可以推导出“不选 变量v”&＃xff08;反过来说也一样&＃xff09;&＃xff0c;这样就是不合法的。换句话说&＃xff0c;点v 和 点v&＃39; 不能在同一个强连通分量中。

求强连通分量的话这里就用一个常规的方法——先从某个点出发DFS遍历能够到达的点&＃xff0c;当退出一个DFS函数时&＃xff0c;将当前的点压入队列中&＃xff08;建议手写队列&＃xff0c;因为这里只是用来储存变量&＃xff09;。

上面是DFS1&＃xff0c;每个点只能遍历一次。

然后依次访问队列中的点&＃xff0c;然后从当前枚举到的队列中的点X出发进行DFS&＃xff0c;将遍历到的点所属的“块”(blk)都设为与点X相同的“块”。这样一个“块”就是一个强连通分量。

最后枚举每一个变量i&＃xff0c;检查 点i 和 点i&＃39; 是否在一个强连通分量中&＃xff0c;如果存在&＃xff0c;则不可行。

举个例子&＃xff1a;HDU 3622 Bomb Game

[题意]

你需要在平面上放n个炸弹——放置第i个炸弹时&＃xff0c;你需要在\((Ax_i,Ay_i)\)和\((Bx_i,By_i)\)两个位置中选择一个位置放置。每个炸弹的爆炸半径都是k&＃xff0c;任意两个炸弹的爆炸范围不能重叠&＃xff08;可以相切&＃xff09;。求k最大为多少。

[解析]

很容易想到二分答案&＃xff0c;放置第i个炸弹时选择 第一个位置 定义为“选择i”&＃xff0c;选择第二个位置 定义为“不选择i”&＃xff0c;这样就形成了一个2-sat问题。

根据二分出来的k可以求出重叠的炸弹&＃xff0c;如果炸弹i与炸弹j重叠&＃xff0c;则说明放炸弹i就不能放炸弹j&＃xff0c;根据这个连边&＃xff0c;2-sat判断合法性即可。

[源代码]

/*Lucky_Glass*/
#include
using namespace std;
const int N&＃61;100,M&＃61;40000;
const double EPS&＃61;1e-5;
int n;struct POINT{int x,y;
}s[N*2&＃43;5];
inline double Dist2(int a,int b){return 1.0*(s[a].x-s[b].x)*(s[a].x-s[b].x)&＃43;1.0*(s[a].y-s[b].y)*(s[a].y-s[b].y);
}struct EDGE{int to,nxt;
}edg1[M&＃43;5],edg2[M&＃43;5];
int hed1[N*2&＃43;5],hed2[N*2&＃43;5];
int cnt1,cnt2;
void AddEdge(int u,int v){ //连边&＃xff0c;正反图都要连edg1[cnt1].to&＃61;v;edg1[cnt1].nxt&＃61;hed1[u];hed1[u]&＃61;cnt1&＃43;&＃43;;edg2[cnt2].to&＃61;u;edg2[cnt2].nxt&＃61;hed2[v];hed2[v]&＃61;cnt2&＃43;&＃43;;
}
void ClearMap(){ //清空图memset(hed1,-1,sizeof hed1);memset(hed2,-1,sizeof hed2);cnt1&＃61;cnt2&＃61;0;
}int Pop[N*2&＃43;5],blk[N*2&＃43;5];
bool vis[N*2&＃43;5];
int blkcnt;
void DFS1(int u){ //求出每个点退出DFS的顺序vis[u]&＃61;true;for(int i&＃61;hed1[u];i!&＃61;-1;i&＃61;edg1[i].nxt)if(!vis[edg1[i].to])DFS1(edg1[i].to);Pop[&＃43;&＃43;Pop[0]]&＃61;u;
}
void DFS2(int u){ //求强连通分量vis[u]&＃61;true;blk[u]&＃61;blkcnt; //blk[i]表示i所属的联通块编号for(int i&＃61;hed2[u];i!&＃61;-1;i&＃61;edg2[i].nxt)if(!vis[edg2[i].to])DFS2(edg2[i].to);
}
bool Check(){Pop[0]&＃61;blkcnt&＃61;0;memset(vis,false,sizeof vis);for(int i&＃61;0;i<2*n;i&＃43;&＃43;)if(!vis[i])DFS1(i);memset(vis,false,sizeof vis);for(int i&＃61;Pop[0];i>&＃61;1;i--) //按照退出顺序if(!vis[Pop[i]]){blkcnt&＃43;&＃43;;DFS2(Pop[i]);}for(int i&＃61;0;i}int main(){while(~scanf("%d",&n)){for(int i&＃61;0;i&＃61;EPS){double mid&＃61;(lef&＃43;rig)/2;ClearMap();for(int i&＃61;0;i}

(坑还没填完&＃xff0c;下一个弄懂再写 TAT)
更新-\(2018/11/17\)&＃xff1b;终于把后面一道题弄懂了

另外一个例子……POJ 3207 Ikki&＃39;s Story IV - Panda&＃39;s Trick

想法比较丰富……另外写一个blog……

\(\mathcal The\ End\)

\(\mathcal Thanks\ for\ reading!\)