首页 > 代码库 > 2-XOR-SAT （种类并查集）
2-XOR-SAT （种类并查集）
写了那么多模拟题这题算是最难的了QAQ
好神，，，我于是补了一下并查集。。
并查集很神。。。。。。
orz
种类并查集。。。orz
对于维护sat，我们可以这样想：
如果x和y的xor是true，那么x和y肯定不一样，那么我们有s[x]=s[y]^1
否则s[x]=s[y]
我们需要维护的是一系列的x和y之间的关系，那么我们考虑用并查集维护这个 区间！
注意这个一定是区间的概念！
因为只有区间才能满足区间性质！
比如
x xor y xor z = true
而我们得知了x xor y的值，那么我们就能知道x xor z的值！
所以x y z可以看成并查集的一条链，然后假设一开始我们只知道y xor z=true 那么连边fa[y]=z 然后 s[y]=s[x]^1
那么当我们得知x xor y=true 时，我们可以将fa[x]=y 然后s[x]=s[y]^1
而现在的图就是
x -> y -> z
我们可以尝试着压缩x到z的路径，使得得出x->z的值 即 fa[x]=z, s[x]^=s[y] 也就是说 x xor z = false
很神奇是不。。
现在我们开始重新定义s数组！
s[i]表示i到i的树根（并查集中的）的xor值
那么根据xor的性质，我们可以在路径压缩里这样写
int f=find(fa[x]); s[x]^=s[fa[x]]; p[x]=f;
那么就可以维护出s了！再一次强调，s表示的是x到树根的xor值！不是它真正的值！（否则就想我一样，一开始怎么想也想不通。。。）
然后我们在合并时，和并查集差不多，只是要维护一下s。即
fx=find(x), fy=find(y)
if(fx!=fy && (x xor y == true)) p[fx]=fy; s[fx]=s[x]^s[y]^1; //这样做的原因很简单，自己想想。。就是根据x xor y=true/false 和 x xor fx=true/false 和 y xor fy=true/false 现在只是要知道fx xor fy = ?。。注意一定不是s[fy]=...因为你看看s的定义。。。。如果是s[fy]=的话，那么p[fx]后边就都乱了。。。
x xor y==false 时也很简单 s[fx]=s[x]^s[y]
判断无解的话就是如果fx == fy 且 x到fx和y到fy的值与所给的x xor y的值不符，那么就是无解。。。
构造解也很简单。我们假设所有的根全都是true
那么问题就简单了。。。。
再路径压缩过后，每个节点到根就是一条路径，那么我们已经知道了根是true。。那么。。不用我说了吧。。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>using namespace std;typedef long long ll;#define pii pair<int, int>#define mkpii make_pair<int, int>#define pdi pair<double, int>#define mkpdi make_pair<double, int>#define pli pair<ll, int>#define mkpli make_pair<ll, int>#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << ‘\t‘; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a<b?a:b; }const int N=1000005;int p[N], s[N], n, m;char c[10];const int ifind(const int x) { if(x==p[x]) return x; int f=ifind(p[x]); s[x]^=s[p[x]]; return p[x]=f;}int main() { read(n); read(m); for1(i, 1, n) p[i]=i; for1(i, 1, m) { int x=getint(), y=getint(), fx=ifind(x), fy=ifind(y); scanf("%s", c); if(c[0]==‘T‘) { if(fx==fy && s[x]==s[y]) { puts("Impossible"); return 0; } if(fx!=fy) p[fx]=fy, s[fx]=s[x]^s[y]^1; } else { if(fx==fy && s[x]!=s[y]) { puts("Impossible"); return 0; } if(fx!=fy) p[fx]=fy, s[fx]=s[x]^s[y]; } } puts("Possible"); for1(i, 1, n) ifind(i); for1(i, 1, n) if(i==p[i]) puts("TRUE"); else s[i]?puts("FALSE"):puts("TRUE"); return 0;}
2-XOR-SAT
【题目描述】
SAT(Satisfiability,可满足性)问题是著名的 NP 完全问题,它的内容是:判断由有
限个布尔变量及其“非”用“或”操作连接起来的表达式组是否可以都为 TRUE。
2-SAT 问题对 SAT 问题做了如下限制:每个表达式由两个变量构成。
XOR-SAT 问题对 SAT 问题做了如下限制:表达式仅由变量与“异或”操作构成。
2-XOR-SAT 问题包含了以上两个限制,即:有 n 个布尔变量x 1 ... x n 与 m 个双变量
异或方程
x a 1 xor x b 1 = c 1
x a 2 xor x b 2 = c 2
{
?
x a m xor x b m = c m
你需要判断方程组是否有解,如果有解请输出任意一组解,否则输出无解。
【输入文件】
第一行两个整数 n m
接下来m行,每行两个整数a i b i 及一个大写字符串c i ,c i 为”TRUE”或”FALSE”
【输出文件】
若无解,则输出一行”Impossible”
若有解,则第一行输出”Possible”,接下来n行输出x 1 ... x n 的值”TRUE”或”FALSE”
【样例输入】
3 2
1 2 TRUE
2 3 FALSE
【样例输出】
Possible
FALSE
TRUE
TRUE【数据范围】
30%的数据保证 n ≤ 20; m ≤ 20
100%的数据保证 1 ≤ n ≤ 100,000; 1 ≤ m ≤ 100,000
2-XOR-SAT （种类并查集）