推荐论文：https://blog.csdn.net/zixiaqian/article/details/4492926
2-SAT问题是2判定性问题，给出n个集合，每个集合中有两个元素，两个元素之一要出现，且有一些元素不能相互共存
考虑每个集合中的元素都为i 和 i'，对于每组信息在他们之间连边，连上边就绑定啦，它们一定要一起选
如果有一个点必须选又必须不选，就是矛盾
有N对物品，每对物品中必须选取一个，也只能选取一个，并且它们之间存在某些限制关系
2-sat中一条有向边的涵义是选了起点就必须选终点
模板：solve表示能否按规则取出，vis中标记为1的元素即为最终取出的元素
bool dfs(int u) { if(vis[u]) return true; if(vis[u^1]) return false; s[cnt++] = u; vis[u] = 1; for(int i = head[u];i;i = nxt[i]) { int v = l[i]; if(!dfs(v)) return false; } return true; } bool solve() { for(int i = 0; i < n; i++) { if(!vis[i<<1] && !vis[i<<1|1]) { cnt = 0; if(!dfs(i<<1)) { while(cnt) vis[s[--cnt]] = false; if(!dfs(i<<1|1)) return false; } } } return true; }
HDU 1814
题意：n个党派要参加会议，每个党派有两个人，要派出一个人去参加，有些人不能同时去，求输出字典序最小的方案
思路：裸题，要求字典序最小就从前面开始搜就可以了
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int maxn = 22010; const int maxm = 40010; const int INF = 1000000100; int head[maxm], nxt[maxm], l[maxm], tot = 0; void build(int f, int t) { l[++tot] = t; nxt[tot] = head[f]; head[f] = tot; } int n, m, cnt, vis[maxn], s[maxn]; void init() { memset(head, 0, sizeof(head)); tot = 0; memset(vis, 0, sizeof(vis)); } bool dfs(int u) { if(vis[u]) return true; if(vis[u^1]) return false; s[cnt++] = u; vis[u] = 1; for(int i = head[u];i;i = nxt[i]) { int v = l[i]; if(!dfs(v)) return false; } return true; } bool solve() { for(int i = 0; i < n; i++) { if(!vis[i<<1] && !vis[i<<1|1]) { cnt = 0; if(!dfs(i<<1)) { while(cnt) vis[s[--cnt]] = false; if(!dfs(i<<1|1)) return false; } } } return true; } int main() { while(~scanf("%d %d", &n, &m)) { init(); for(int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); build(a-1, (b-1)^1); build(b-1, (a-1)^1); } if(solve()) { for(int i = 0; i < n; i++) { if(vis[i<<1]) printf("%d ", i<<1|1); else printf("%d ", (i<<1)+2); } } else printf("NIE "); } return 0; }
POJ 3648
题意：有n-1对夫妇参加新娘新郎的婚礼，每对夫妇要坐对面，且有些对有（奸情）的不能同时坐在新娘的对面，问新娘这一侧都坐了谁
思路：看起来就是2-SAT问题，每一对夫妇是一个集合
因为新娘这一侧是可以有冲突的！！所以要考虑我们求新娘对面都坐了谁
这样的话我们就不能选新娘
连一条新娘向新郎的边，如果选了新娘，那么就要选新郎，就产生冲突了，判为不行
思路好神奇哇
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int maxn = 22010; const int maxm = 100010; const int INF = 1000000100; int head[maxm], nxt[maxm], l[maxm], tot = 0; void build(int f, int t) { l[++tot] = t; nxt[tot] = head[f]; head[f] = tot; } int n, m, cnt, vis[maxn], s[maxn]; void init() { memset(head, 0, sizeof(head)); tot = 0; memset(vis, 0, sizeof(vis)); } bool dfs(int u) { if(vis[u]) return true; if(vis[u^1]) return false; s[cnt++] = u; vis[u] = 1; for(int i = head[u];i;i = nxt[i]) { int v = l[i]; if(!dfs(v)) return false; } return true; } bool solve() { for(int i = 0; i < n; i++) { if(!vis[i<<1] && !vis[i<<1|1]) { cnt = 0; if(!dfs(i<<1)) { while(cnt) vis[s[--cnt]] = false; if(!dfs(i<<1|1)) return false; } } } return true; } int cal(int x, char c) { if(c == 'h') return x<<1; if(c == 'w') return x<<1|1; } int main() { while(1) { scanf("%d %d", &n, &m); if(n == 0 && m == 0) break; init(); for(int i = 0; i < m; i++) { int a, b; char c, d; scanf("%d%c%d%c", &a, &c, &b, &d); a = cal(a, c); b = cal(b, d); build(a, b^1); build(b, a^1); } build(1, 0); if(solve()) { for(int i = 1; i < n; i++) { if(i > 1) printf(" "); printf("%d", i); if(vis[i<<1]) printf("w"); else printf("h"); } printf(" "); } else printf("bad luck "); } return 0; }
题意：0 ~ n-1这n个数，给出两个数之间AND OR 或者 XOR的值，问能否推断出这几个数都是什么
思路：n个数对应n个集合，每个数为0或1对应一个集合中的i 和 i'，
a and b == 1, 这种情况a和b必须取1，所以连边a’->a, b’->b.
a and b == 0, 这种情况a和b不能同时为1，所以连边a->b’, b->a’.
a or b == 1, 这种情况a和b不能同时为0，所以连边a’->b, b’->a.
a or b == 0, 这种情况a和b必须同时为0，所以连边a->a’, b->b’.
a xor b == 1, 这种情况a和b取值要相反，所以连边a->b’, a’->b, b->a’, b’->a.
a xor b == 0, 这种情况a和b取值要相同，所以连边a->b, b->a, a’->b’, b’->a’.
也可以这么想：
x,y代表当前的式子未知数..x0为x选0的点..x1为x选1的点...y0,y1同样..
1、x AND y = 1 .. 表明x , y必须为1...所以不能选择x0,y0...这个东西要表示出来..就让选择x0,y0直接就自我矛盾..加边 ( x0,x1 ) , ( y0,y1 )
2、x AND y = 0 ..表明x,y至少有一个为0...那么加边 ( x1,y0 ) , ( y1,x0 )
3、x OR y = 1 ...表明x,y至少有一个味1..那么加边 ( x0,y1 ) , ( y0,x1 )
4、x OR y = 0..表明x,y都为0...所以让选择x1,y1就直接自矛盾 ( x1,x0 ) , ( y1,y0 )
5、x XOR y = 1..表明x,y不同..那么加边 ( x0,y1 ) , ( x1,y0 ) ,( y0,x1 ) , ( y1,x0 )
6、x XOR y = 0..表明x,y是相同的..那么加边 ( x0,y0 ) , ( x1,y1 ) ,( y0,x0 ) , ( y1,x1 )
tarjan看一个集合中的两个点是不是在同一个环里，在的话就凉凉
主要还是在于建图
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int SZ = 4000010; const int INF = 1000000100; int head[SZ], nxt[SZ], l[SZ], tot = 0; void build(int f, int t) { l[++tot] = t; nxt[tot] = head[f]; head[f] = tot; } int n, m; stack<int> s; int dfn[10010], low[10010], clock = 0; int sccnum[10010], cnt = 0; void dfs(int u) { dfn[u] = low[u] = ++clock; s.push(u); for(int i = head[u]; i; i = nxt[i]) { int v = l[i]; if(!dfn[v]) { dfs(v); low[u] = min(low[u], low[v]); } else if(!sccnum[v]) low[u] = min(low[u], dfn[v]); } if(low[u] == dfn[u]) { cnt++; while(1) { int v = s.top(); s.pop(); sccnum[v] = cnt; if(u == v) break; } } } void tarjan() { for(int i = 0; i < n<<1; i++) if(!dfn[i]) dfs(i); } void init() { memset(head, 0, sizeof(head)); tot = 0; memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); clock = 0; while(s.size()) s.pop(); cnt = 0; memset(sccnum, 0, sizeof(sccnum)); } int main() { while(~scanf("%d %d", &n, &m)) { init(); for(int i = 0; i < m; i++) { int a, b, c; char op[6]; scanf("%d%d%d%s", &a, &b, &c, op); if(op[0] == 'A') { if(c == 1) build(a<<1|1, a<<1), build(b<<1|1, b<<1); if(c == 0) build(a<<1, b<<1|1), build(b<<1, a<<1|1); } if(op[0] == 'O') { if(c == 1) build(a<<1|1, b<<1), build(b<<1|1, a<<1); if(c == 0) build(a<<1, a<<1|1), build(b<<1, b<<1|1); } if(op[0] == 'X') { if(c == 1) build(a<<1, b<<1|1), build(a<<1|1, b<<1), build(b<<1, a<<1|1), build(b<<1|1, a<<1); if(c == 0) build(a<<1, b<<1), build(b<<1, a<<1), build(a<<1|1, b<<1|1), build(b<<1|1, a<<1|1); } } tarjan(); bool flag = true; for(int i = 0; i < n; i++) if(sccnum[i<<1] == sccnum[i<<1|1]) flag = false; if(flag) printf("YES "); else printf("NO "); } return 0; }
POJ 3207
题意：一个圈上顺着排0,1,...,n-1号点，给出m条边，每条边可以从圆内走也可以从圆外走，问这些边可不可以不相交
思路：对于每条Link，要么在圆外，要么在圆内，且不可同时满足，只能两者取一，判断这M条Link是否合法，也就是M条Link不冲突，这就是典型的2-sat问题了。
将每条Link i 看做一个点，如果Link在圆内，则选做i ，如果在圆外， 则选做i'。对于两条线(i,j) ，如果i，j不能同时在圆内，也就可以推出两者不能同时在圆外
如果这两条边冲突，那么balabala连边
构图方式神奇↓
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <algorithm> #include <stack> using namespace std; const int maxn = 600000; const int maxm = 600010; const int INF = 1000000100; int head[maxm], nxt[maxm], l[maxm], tot = 0; struct Edge { int f, t; }e[550]; void build(int f, int t) { l[++tot] = t; nxt[tot] = head[f]; head[f] = tot; } int n, m, cnt, vis[maxn], s[maxn]; void init() { memset(head, 0, sizeof(head)); tot = 0; memset(vis, 0, sizeof(vis)); } bool dfs(int u) { if(vis[u]) return true; if(vis[u^1]) return false; s[cnt++] = u; vis[u] = 1; for(int i = head[u]; i; i = nxt[i]) { int v = l[i]; if(!dfs(v)) return false; } return true; } bool solve() { for(int i = 0; i < m; i++) { if(!vis[i<<1] && !vis[i<<1|1]) { cnt = 0; if(!dfs(i<<1)) { while(cnt) vis[s[--cnt]] = false; if(!dfs(i<<1|1)) return false; } } } return true; } int main() { scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); e[i].f = min(a, b); e[i].t = max(a, b); } for(int i = 0; i < m; i++) for(int j = i+1; j < m; j++) if((e[j].f<e[i].f && e[j].t<e[i].t && e[j].t>e[i].f) || (e[j].f>e[i].f && e[j].f<e[i].t && e[j].t>e[i].t)) { build(i<<1, j<<1|1); build(j<<1, i<<1|1); build(i<<1|1, j<<1); build(j<<1|1, i<<1); } if(solve()) printf("panda is telling the truth... "); else printf("the evil panda is lying again "); return 0; }