给定 \(n\) 个 bool 变量和它们的一些关系，求一组合法解或报告误解。
我们给每个 bool 变量建两个点，分别表示当前状态是 0 还是 1。
对于每一条形似若 \(a \space =\space x\) ，则 \(b \space =\space y\) 的判定（其中 \(a,\space b\) 是变量，\(x,\space y\) 是 bool 值），我们从 \(a\) 的 \(x\) 状态向 \(b\) 的 \(y\) 状态连一条边。
对于建出的图跑 tarjan 缩点，若同一变量的两种状态在同一 scc 里，则无解；
否则我们对于每个变量取拓扑序较大的那个状态。
P4782 【模板】2-SAT
有 \(n\) 个布尔变量 \(x_1\sim x_n\)，另有 \(m\) 个需要满足的条件，每个条件的形式都是 「\(x_i\) 为 true / false 或 \(x_j\) 为 true / false」。比如 「\(x_1\) 为真或 \(x_3\) 为假」、「\(x_7\) 为假或 \(x_2\) 为假」。
#include <bits/stdc++.h>using namespace std;namespace mine {const int N = 2000010;const int BUFSIZE = 1 << 20;char ibuf[BUFSIZE], *is = ibuf,*IT = ibuf;char tmp[BUFSIZE]; int CNT = 0;inline char getch() {if(is== IT) IT = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); return is == IT ? EOF :*is ++;}int readInt() {int x = 0, y = 0; char c = 0; while(!isdigit(c)) y |= c == '-', c = getch(); while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return !y ? x : -x; }int readLL() {LL x = 0, y = 0; char c = 0; while(!isdigit(c)) y |= c == '-', c = getch(); while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return !y ? x : -x; }void flush() { fwrite(tmp, 1, CNT, stdout); CNT = 0; }void putch(char c) { tmp[CNT ++] = c; if(CNT == BUFSIZE) flush(); }void putint(int x) {char Q[20];int tp = 0; if(x < 0) putch('-'), x = -x; if(x == 0) putch('0'); while(x) Q[tp ++]=(x % 10 + '0'), x /= 10; while(tp --) putch(Q[tp]); }void putLL(LL x) {char Q[20];int tp = 0; if(x < 0) putch('-'), x = -x; if(x == 0) putch('0'); while(x) Q[tp ++]=(x % 10 + '0'), x /= 10; while(tp --) putch(Q[tp]); }struct Basic {Basic &operator >> (int &A){ A = mine::readInt(); return (*this); }Basic &operator >> (LL &A){ A = mine::readLL(); return (*this); }Basic &operator << (const int &A) { putint(A); return (*this); }Basic &operator << (const LL &A) { putLL(A); return (*this); }Basic &operator << (const char &A) { putch(A); return (*this); }Basic &operator << (const string &A) { for(char c : A) putch(c); return (*this); }void Flush() { flush(); }} ccin,ccout;
}
using namespace mine;int n, m;
int a[N];
vector<int> G[N];
int dfn[N], low[N], cur;
int s[N], t, ins[N];
int bl[N], cnt;void tarjan(int u) {dfn[u] = low[u] = ++ cur;s[++ t] = u; ins[u] = 1;for(int v : G[u]) {if(!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]);} else if(ins[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]) {int la = 0; ++ cnt;do {la = s[t]; ins[s[t --]] = 0;bl[la] = cnt; a[la / 2] = la & 1;} while(la != u);}
}int main() {ccin >> n >> m;for(int i = 1; i <= m; ++ i) {int a, x, b, y;ccin >> a >> x >> b >> y;G[a * 2 + x].pb(b * 2 + (y ^ 1));G[b * 2 + y].pb(a * 2 + (x ^ 1));}for(int i = 1; i <= n * 2; ++ i)if(!dfn[i]) tarjan(i);for(int i = 1; i <= n; ++ i)if(bl[i * 2] == bl[i * 2 + 1]) {ccout << "IMPOSSIBLE"; flush();return 0;}cout << "POSSIBLE\n";for(int i = 1; i <= n; ++ i) ccout << a[i] << ' ';flush();return 0;
}
P3513 [POI 2011] KON-Conspiracy
给定 \(n\) 个点的无向图，问将整张图分为一个独立集和一个完全子图的方案数。
先 2-SAT 求出一组合法解，
\(1\) 表示在独立集
\(0\) 表示在完全子图
然后考虑每组拿出 \(0\) 到 \(1\) 个点扔到对面计算方案
点击查看代码
#include <bits/stdc++.h>using namespace std;namespace mine {typedef long long LL;typedef unsigned long long ULL;const int N = 5010;const int Mod = 998244353;#define pii pair<int, int>#define pll pair<LL, LL>#define fi first#define se second#define pb push_back#define eb emplace_back#define re registervoid chkmx(int &x, int y) { if(y > x) x = y; }void chkmx(LL &x, LL y) { if(y > x) x = y; }void chkmn(int &x, int y) { if(y < x) x = y; }void chkmn(LL &x, LL y) { if(y < x) x = y; }void adds(int &x, int y) { x += y; }void adds(LL &x, LL y) { x += y; }void adds(LL &x, LL y, LL Mod) { x += y; if(x >= Mod) x -= Mod; if(x < 0) x += Mod; }void mul(int &x, int y) { x = x * y; }void mul(LL &x, LL y) { x = x * y; }void mul(LL &x, LL y, LL Mod) { x = x * y % Mod; }LL q_pow(LL x, LL y, LL Mod) {LL s = 1 % Mod;for(; y; y >>= 1, mul(x, x, Mod)) if(y & 1) mul(s, x, Mod);return s;}LL Inv(LL x, LL Mod) { return q_pow(x, Mod - 2, Mod); }int popcnt(int x) { return __builtin_popcount(x); }int popcnt(LL x) { return __builtin_popcountll(x); }int lowbit(int x) { return x & (-x); }LL lowbit(LL x) { return x & (-x); }struct BIT {int tr[N], n;void init(int x) { n = x; for(int i = 0; i <= n; ++ i) tr[i] = 0;}void upd(int x, int y) { for(; x <= n; x += lowbit(x)) adds(tr[x], y); }int ask(int x) { int s = 0; for(; x; x -= lowbit(x)) s += tr[x]; return s; }int query(int l, int r) { if(l > r) return 0; return ask(r) - ask(l - 1); }};const int BUFSIZE = 1 << 20;char ibuf[BUFSIZE], *is = ibuf,*IT = ibuf;char tmp[BUFSIZE]; int CNT = 0;inline char getch() {if(is== IT) IT = (is = ibuf) + fread(ibuf, 1, BUFSIZE, stdin); return is == IT ? EOF :*is ++;}int readInt() {int x = 0, y = 0; char c = 0; while(!isdigit(c)) y |= c == '-', c = getch(); while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return !y ? x : -x; }int readLL() {LL x = 0, y = 0; char c = 0; while(!isdigit(c)) y |= c == '-', c = getch(); while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getch(); return !y ? x : -x; }void flush() { fwrite(tmp, 1, CNT, stdout); CNT = 0; }void putch(char c) { tmp[CNT ++] = c; if(CNT == BUFSIZE) flush(); }void putint(int x) {char Q[20];int tp = 0; if(x < 0) putch('-'), x = -x; if(x == 0) putch('0'); while(x) Q[tp ++]=(x % 10 + '0'), x /= 10; while(tp --) putch(Q[tp]); }void putLL(LL x) {char Q[20];int tp = 0; if(x < 0) putch('-'), x = -x; if(x == 0) putch('0'); while(x) Q[tp ++]=(x % 10 + '0'), x /= 10; while(tp --) putch(Q[tp]); }struct Basic {Basic &operator >> (int &A){ A = mine::readInt(); return (*this); }Basic &operator >> (LL &A){ A = mine::readLL(); return (*this); }Basic &operator << (const int &A) { putint(A); return (*this); }Basic &operator << (const LL &A) { putLL(A); return (*this); }Basic &operator << (const char &A) { putch(A); return (*this); }Basic &operator << (const string &A) { for(char c : A) putch(c); return (*this); }void Flush() { flush(); }} ccin,ccout;
}
using namespace mine;int n, ans;
int a[N][N], c[N], r[N];
vector<int> G[N << 1], t[2];
int dfn[N << 1], low[N << 1], cur;
int s[N << 1], ins[N << 1], tt;
int bl[N << 1], cnt;void tarjan(int u) {dfn[u] = low[u] = ++ cur;s[++ tt] = u; ins[u] = 1;for(int v : G[u]) {if(!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]);} else if(ins[v]) low[u] = min(low[u], dfn[v]);}if(dfn[u] == low[u]) {int la = 0; ++ cnt;do {la = s[tt]; -- tt;ins[la] = 0; bl[la] = cnt;r[la / 2] = la & 1;} while(la != u);}
}int main() {ccin >> n;for(int i = 1; i <= n; ++ i) {int x; ccin >> x;while(x --) {int y; ccin >> y;a[i][y] = a[y][i] = 1;}r[i] = -1;for(int j = 1; j <= n; ++ j) {if(i == j) continue;if(a[i][j]) G[i * 2 + 1].pb(j * 2);else G[i * 2].pb(j * 2 + 1);}}for(int i = 1; i <= n * 2; ++ i)if(!dfn[i]) tarjan(i);for(int i = 1; i <= n; ++ i)if(bl[i * 2] == bl[i * 2 + 1]) {ccout << 0; flush(); return 0;}for(int i = 1; i <= n; ++ i) {t[r[i]].pb(i);for(int j = 1; j <= n; ++ j)if(a[i][j] && r[i] != r[j]) ++ c[i];}int flag = (t[0].size() && t[1].size());for(int x : t[0]) if(c[x] == t[1].size() && t[0].size() >= 2) ++ ans;for(int x : t[1]) if(c[x] == 0 && t[1].size() >= 2) ++ ans;for(int x : t[0]) for(int y : t[1]) {if(a[x][y]) { -- c[x]; -- c[y]; }if(c[x] == t[1].size() - 1 && c[y] == 0 && flag) ++ ans;if(a[x][y]) { ++ c[x]; ++ c[y]; }}ccout << ans + flag; flush();return 0;
}