[学习笔记] 2-SAT
一、2-SAT
2-SAT 问题是给定 \(n\) 个变量 \(x_1, x_2, \dots, x_n\)，取值只有 \(0\) 或 \(1\)，然后这些变量要满足一些条件，比如：如果 \(x_1 = 1\) 那么 \(x_2 = 0\) 之类的。
然后我们要解决的问题就是判定是否存在一组 \((x_1, x_2, \dots, x_n)\) 满足条件，如果存在输出方案。
考虑建图。将每个变量 \(x_i\) 建成两个点，\(i_0\) 和 \(i_1\)，即 \(x_i = 0\) 和 \(x_i = 1\)。从 \(i_k\) 连到 \(j_l\) 就表示推理如果 \(x_i = k\) 那么 \(x_j = l\)。
然后我们要判断是否有解。先对原图缩强连通分量，如果 \(i_0\) 和 \(i_1\) 在同一个 SCC 里就矛盾，即无解；就是如果 \(x_i = 0\) 可以推到 \(x_i = 1\)，又可以推到 \(x_i = 0\)，显然矛盾。
考虑输出方案，设 \(scc_u\) 表示节点 \(u\) 所在的 SCC 的编号。如果 \(scc_{i_0} > scc_{i_1}\)，那么说明 \(i_0\) 的拓扑序在 \(i_1\) 之前，说明 \(x_i = 1\)，否则 \(x_i = 0\)。
下面给出模板题 https://www.luogu.com.cn/problem/P4782 的代码：
/**
* author : OMG_78
* created: 2023-07-16-15.56.00
**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline bool ok (char c) {
if (c < '0') return true;
if (c > '9') return true;
return false;
}
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; ok (c) ; c = getchar ()) f = (c == '-') ? 1 : f;
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
const int N = 2e6 + 5;
vector < int > G[N];
int n, m, dfn[N], low[N], isin[N], time_click, scc[N], cnt;
vector < int > sccs[N];
stack < int > stk;
inline void tarjan (int u) {
low[u] = dfn[u] = ++ time_click;
isin[u] = 1;
stk.push (u);
for (int v : G[u]) {
if (!dfn[v]) {tarjan (v), low[u] = min (low[u], low[v]);}
else {if (isin[v]) low[u] = min (low[u], dfn[v]);}
}
if (dfn[u] == low[u]) {
cnt ++;
while (true) {
int v = stk.top (); scc[v] = cnt, isin[v] = 0, stk.pop ();
if (u == v) break;
}
}
}
inline void add_edge (int u, int v) {
G[u].push_back (v);
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n), read (m);
for (int _ = 1;_ <= m; ++ _) {
int i, a, j, b;
read (i), read (a), read (j), read (b);
add_edge (i + (a ^ 1) * n, j + b * n);
add_edge (j + (b ^ 1) * n, i + a * n);
}
for (int i = 1;i <= 2 * n; ++ i) {
if (!dfn[i]) tarjan (i);
}
for (int i = 1;i <= n; ++ i) {
if (scc[i] == scc[i + n]) {
printf ("IMPOSSIBLE\n");
return 0;
}
}
printf ("POSSIBLE\n");
for (int i = 1;i <= n; ++ i) {
if (scc[i] > scc[i + n]) printf ("1 ");
else printf ("0 ");
}
printf ("\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
二、洛谷 P4171 [JSOI2010] 满汉全席
https://www.luogu.com.cn/problem/P4171
很裸的一道题。
把 h 看成 \(1\)，m 看成 \(0\)，然后跑一遍板子即可，甚至连方案都不用输出 hhh。
多测记得清空。
/**
* author : OMG_78
* created: 2023-07-16-16.22.26
**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline bool ok (char c) {
if (c < '0') return true;
if (c > '9') return true;
return false;
}
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; ok (c) ; c = getchar ()) f = (c == '-') ? 1 : f;
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
const int N = 200 + 5;
vector < int > G[N];
int n, m, dfn[N], low[N], isin[N], time_click, scc[N], cnt;
stack < int > stk;
inline void tarjan (int u) {
low[u] = dfn[u] = ++ time_click;
isin[u] = 1;
stk.push (u);
for (int v : G[u]) {
if (!dfn[v]) {tarjan (v), low[u] = min (low[u], low[v]);}
else {if (isin[v]) low[u] = min (low[u], dfn[v]);}
}
if (dfn[u] == low[u]) {
cnt ++;
while (true) {
int v = stk.top (); scc[v] = cnt, isin[v] = 0, stk.pop ();
if (u == v) break;
}
}
}
inline void add_edge (int u, int v) {
G[u].push_back (v);
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
int _; read (_);
while (_ --) {
read (n), read (m);
for (int i = 1;i <= 2 * n; ++ i) G[i].clear ();
for (int i = 1;i <= 2 * n; ++ i) dfn[i] = low[i] = isin[i] = scc[i] = 0;
time_click = cnt = 0;
for (int i = 1;i <= m; ++ i) {
char s[10], t[10];
int x, y;
scanf ("%s %s", s, t);
x = y = 0;
int ls = strlen (s), lt = strlen (t);
for (int j = 1;j < ls; ++ j) x = (x * 10 + s[j] - '0');
for (int j = 1;j < lt; ++ j) y = (y * 10 + t[j] - '0');
int a = (s[0] == 'h');
int b = (t[0] == 'h');
add_edge (x + (a ^ 1) * n, y + b * n);
add_edge (y + (b ^ 1) * n, x + a * n);
}
for (int i = 1;i <= 2 * n; ++ i) {
if (!dfn[i]) tarjan (i);
}
int ok = 1;
for (int i = 1;i <= n; ++ i) {
if (scc[i] == scc[i + n]) ok = 0;
}
if (ok) printf ("GOOD\n");
else printf ("BAD\n");
}
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
三、洛谷 P5782 [POI2001] 和平委员会
https://www.luogu.com.cn/problem/P5782
裸题，不讲。
/**
* author : OMG_78
* created: 2023-07-16-16.34.29
**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline bool ok (char c) {
if (c < '0') return true;
if (c > '9') return true;
return false;
}
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; ok (c) ; c = getchar ()) f = (c == '-') ? 1 : f;
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
const int N = 2 * 8000 + 5;
vector < int > G[N];
int n, m, dfn[N], low[N], isin[N], time_click, scc[N], cnt;
stack < int > stk;
inline void tarjan (int u) {
low[u] = dfn[u] = ++ time_click;
isin[u] = 1;
stk.push (u);
for (int v : G[u]) {
if (!dfn[v]) {tarjan (v), low[u] = min (low[u], low[v]);}
else {if (isin[v]) low[u] = min (low[u], dfn[v]);}
}
if (dfn[u] == low[u]) {
cnt ++;
while (true) {
int v = stk.top (); scc[v] = cnt, isin[v] = 0, stk.pop ();
if (u == v) break;
}
}
}
inline void add_edge (int u, int v) {
G[u].push_back (v);
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n), read (m);
for (int i = 1;i <= m; ++ i) {
int x, y;
read (x), read (y);
int kx = (x + 1) / 2, ky = (y + 1) / 2;
int a = x % 2, b = y % 2;
add_edge (kx + a * n, ky + (b ^ 1) * n);
add_edge (ky + b * n, kx + (a ^ 1) * n);
}
for (int i = 1;i <= 2 * n; ++ i) {
if (!dfn[i]) tarjan (i);
}
for (int i = 1;i <= n; ++ i) {
if (scc[i] == scc[i + n]) {
printf ("NIE\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
}
for (int i = 1;i <= n; ++ i) {
if (scc[i] > scc[i + n]) printf ("%d\n", 2 * (i - 1) + 1);
else printf ("%d\n", 2 * i);
}
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
四、洛谷 P3007 [USACO11JAN] The Continental Cowngress G
https://www.luogu.com.cn/problem/P3007
也是裸题。
有个地方，就是判断取节点 \(u\) 是否合法，只需要判断一下这样 bfs 会不会搜到两个矛盾的点即可。
具体见代码。
/**
* author : OMG_78
* created: 2023-07-16-16.58.05
**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline bool ok (char c) {
if (c < '0') return true;
if (c > '9') return true;
return false;
}
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; ok (c) ; c = getchar ()) f = (c == '-') ? 1 : f;
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
const int N = 2 * 1000 + 5;
vector < int > G[N];
int n, m, dfn[N], low[N], isin[N], time_click, scc[N], cnt;
stack < int > stk;
inline void tarjan (int u) {
low[u] = dfn[u] = ++ time_click;
isin[u] = 1;
stk.push (u);
for (int v : G[u]) {
if (!dfn[v]) {tarjan (v), low[u] = min (low[u], low[v]);}
else {if (isin[v]) low[u] = min (low[u], dfn[v]);}
}
if (dfn[u] == low[u]) {
cnt ++;
while (true) {
int v = stk.top (); scc[v] = cnt, isin[v] = 0, stk.pop ();
if (u == v) break;
}
}
}
inline void add_edge (int u, int v) {
G[u].push_back (v);
}
int vis[N];
inline void dfs (int u) {
if (vis[u]) return ;
vis[u] = 1;
for (int v : G[u]) dfs (v);
}
inline bool check (int u) {
for (int i = 1;i <= 2 * n; ++ i) vis[i] = 0;
dfs (u);
for (int i = 1;i <= n; ++ i) {
if (vis[i] && vis[i + n]) return false;
}
return true;
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n), read (m);
for (int i = 1;i <= m; ++ i) {
int x, y;
char s[5], t[5];
scanf ("%d %s %d %s", &x, s, &y, t);
int vx = (s[0] == 'Y'), vy = (t[0] == 'Y');
add_edge (x + (vx ^ 1) * n, y + vy * n);
add_edge (y + (vy ^ 1) * n, x + vx * n);
}
for (int i = 1;i <= 2 * n; ++ i) {
if (!dfn[i]) tarjan (i);
}
for (int i = 1;i <= n; ++ i) {
if (scc[i] == scc[i + n]) {
printf ("IMPOSSIBLE\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
}
for (int i = 1;i <= n; ++ i) {
bool _0 = check (i);
bool _1 = check (i + n);
if (_0 && !_1) printf ("N");
else if (!_0 && _1) printf ("Y");
else printf ("?");
}
printf ("\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/