闲话 10.10

想到什么写什么

---

昨晚

CTH（大喊）：HDK！

HDK（大喊）：CTH！

CTH（愣了一下）：干啥？

---

2-SAT

定义

给出若干个形如 \(a\lor b\) 的限制条件，询问是否有满足条件的一组解。

人话：给出 \(n\) 个集合，每个集合两个元素，再给定若干个限制条件 \(\left \langle a,b\right \rangle\) 表示 \(a\) 与 \(b\) 矛盾，询问在这 \(n\) 个集合中各选一个能否满足所有限制条件。

思路

考虑转化限制条件。已知 \(a\lor b\) 为真，则当 \(\lnot a\) 为真时 \(b\) 必为真，简单推一下可得：

\[\lnot a\to b,\lnot b \to a \]

这样模型就构建出来了，我们可以将其转化成图来做。

考虑这样连边的含义，若起点为真则终点必为真，那么若成环则表示这些点同时为真或假，我们可以用 tarjan 将它们缩成一个点。

判断有无解的办法是看 \(a\) 与 \(\lnot a\) 的点是否缩成同一个点，若是则显然无解，否则有解。

若要输出方案，一种合法的构造是判断 \(a\) 与 \(\lnot a\) 缩点的先后，先缩为真。

实现

【模板】2-SAT

直接按思路做即可。

点击查看代码

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 2e6 + 5;
int n, m;
int dfn[N], low[N], tot, bl[N], num;
int hh[N], to[N << 1], ne[N << 1], cnt;
stack<int> st;
namespace Wisadel
{void Wadd(int u, int v){to[++cnt] = v;ne[cnt] = hh[u];hh[u] = cnt;}void Wtarjan(int u){dfn[u] = low[u] = ++tot, st.push(u);for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(!dfn[v]){Wtarjan(v);low[u] = min(low[u], low[v]);}else if(!bl[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){++num;while(st.size()){int zc = st.top(); st.pop();bl[zc] = num;if(zc == u) break;}}}short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);n = qr, m = qr;memset(hh, -1, sizeof hh);fo(i, 1, m){int x = qr, v1 = qr, y = qr, v2 = qr;if(v1 && v2) Wadd(x + n, y), Wadd(y + n, x);if(v1 && !v2) Wadd(x + n, y + n), Wadd(y, x);if(!v1 && v2) Wadd(x, y), Wadd(y + n, x + n);if(!v1 && !v2) Wadd(x, y + n), Wadd(y, x + n);}fo(i, 1, 2 * n) if(!dfn[i]) Wtarjan(i);bool can = 1;fo(i, 1, n) if(bl[i] == bl[i + n]){can = 0; break;}if(!can) puts("IMPOSSIBLE");else{puts("POSSIBLE");fo(i, 1, n) printf("%d ", (bl[i] < bl[i + n]));}return Ratio;}
}
int main(){return Wisadel::main();}

例题

[JSOI2010] 满汉全席

每一种食材不是满就是汉，比较能看出来是 2-SAT，看出来后就是纯板子了。

点击查看代码

#include<bits/stdc++.h>
#define fo(x, y, z) for(register int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(register int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
#define lx ll
inline lx qr()
{char ch = getchar();lx x = 0 , f = 1;for(;ch<'0'||ch>'9';ch = getchar()) if(ch == '-') f = -1;for(;ch>= '0' && ch<= '9';ch = getchar()) x = (x<<3) + (x<<1) + (ch^48);return x*f;
}
#undef lx
#define qr qr()
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second
const int Ratio = 0;
const int N = 1e5 + 5;
int m, n;
int dfn[N], low[N], tot, bl[N], num;
int hh[N], to[N << 1], ne[N << 1], cnt;
stack<int> st;
namespace Wisadel
{void Wadd(int u, int v){to[++cnt] = v;ne[cnt] = hh[u];hh[u] = cnt;}void Wtarjan(int u){dfn[u] = low[u] = ++tot, st.push(u);for(int i = hh[u]; i != -1; i = ne[i]){int v = to[i];if(!dfn[v]){Wtarjan(v);low[u] = min(low[u], low[v]);}else if(!bl[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]){num++;while(st.size()){int zc = st.top(); st.pop();bl[zc] = num;if(zc == u) break;}}}short main(){// freopen(".in", "r", stdin) , freopen(".out", "w", stdout);int T = qr;while(T--){n = qr, m = qr;cnt = num = tot = 0;memset(hh, -1, sizeof hh);memset(bl, 0, sizeof bl);memset(dfn, 0, sizeof dfn);fo(i, 1, m){string s1, s2; cin >> s1 >> s2;int l1 = s1.size(), l2 = s2.size();int v1 = 0, v2 = 0;fo(j, 1, l1 - 1) v1 = v1 * 10 + s1[j] - '0';fo(j, 1, l2 - 1) v2 = v2 * 10 + s2[j] - '0';if(s1[0] == 'm' && s2[0] == 'm') Wadd(v1 + n, v2), Wadd(v2 + n, v1);if(s1[0] == 'm' && s2[0] == 'h') Wadd(v1 + n, v2 + n), Wadd(v2, v1);if(s1[0] == 'h' && s2[0] == 'm') Wadd(v1, v2), Wadd(v2 + n, v1 + n);if(s1[0] == 'h' && s2[0] == 'h') Wadd(v1, v2 + n), Wadd(v2, v1 + n);}fo(i, 1, 2 * n) if(!dfn[i]) Wtarjan(i);bool can = 1;fo(i, 1, n) if(bl[i] == bl[i + n]){can = 0; break;}if(!can) puts("BAD");else puts("GOOD");}return Ratio;}
}
int main(){return Wisadel::main();}

---

发现要用到 tarjan，但是大部分忘了，所以复习。

Tarjan 求点双，缩点

感觉现阶段再看 tarjan 好理解了不少。

\(dfn_u\) 为点 \(u\) 的 dfs 序，\(low_u\) 是点 \(u\) 能通过返祖边返回到的最小的节点的 dfs 序。

后面仙姑。