当前位置: 首页 > news >正文

2-SAT

给定 \(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;
}
http://www.hskmm.com/?act=detail&tid=34545

相关文章:

  • CSP-S模拟10
  • CSP-S模拟赛加赛 比赛总结
  • 我要好好写博客了 - Milo
  • 洛谷P4735--最大异或和
  • DAPO代码实现浅析
  • [KaibaMath]1011 关于收敛数列保号性的证明
  • Appium 3.0:跨平台移动自动化测试框架全面解析
  • 赛前训练 12 extra 树上差分倍增
  • 塔吊施工人员操作合规性监测!思通数科 AI 卫士实时守护作业安全
  • Dos命令1
  • 题解:P1073 [NOIP 2009 提高组] 最优贸易
  • 吩咐
  • 互评五
  • 机器人技术新前沿:自动驾驶路径规划算法解析
  • 前端框架文档新思路:基于源码解析的自动化方案
  • 常用模板
  • C++ std::forwardT 的使用
  • tryhackme-预安全-网络基础知识-数据包和帧-07
  • 迈向零信任存储:基于RustFS构建内生安全的数据架构
  • 如果这就是人类脑海的话 雪白纸上划出血红层层痕迹 不如杀死这些记忆
  • 嗣澳——扫,墨依奥——描,希伊桉——线
  • 服务器被攻击!原因竟然是他?真没想到...
  • 得到的眼泪学会了哭泣 得到的悲伤缓慢摧残肉体 被所爱之人踩在地
  • 框架架构的多维赋能——论其对自然语言处理深层语义分析的影响与启示
  • 使用 robocopy 命令备份还原数据速度统计
  • 顺天地之自然
  • Mac 打开终端方式
  • PWN手的成长之路-20-cgpwn2
  • 树状数组和线段树基础
  • C++ofstream写文件bug