想到什么写什么
昨晚
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\) 缩点的先后，先缩为真。
实现
直接按思路做即可。
点击查看代码
#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();}
例题
每一种食材不是满就是汉，比较能看出来是 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 序。
后面仙姑。
标签：int,闲话,v1,v2,dfn,low,Wadd,10.10 From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18456050