2 - SAT 适定性问题
解决问题可食用范围
有 n 个非 0 及 1 的变量 a[i]，满足以下 m 个条件：
问题描述
如果 a[i] 为 x，则 a[j] 为 y。
解决思路
我们仍然要先将其转化为 图论问题，首先我们把每一个 a[i] 分成两个点：i，i+n，表示 a[i] = 0，a[i] = 1。
对于一条边 (u,v)，表示如果 u%n 为 u/n 则 v%n 为 v/n。
然后我们就可以建出一个有向图。
示例输入
| 4 8
1 0 2 1
4 0 2 1
3 0 1 1
1 1 3 1
3 1 4 1
4 1 1 1
2 0 3 1
2 1 3 0
|
我们可以发现：
-
如果两个属于同一元素的节点在一条链上时，越靠近末尾的就是答案。
-
且对于在一个 scc 内的元素，他们要不是同时满足，要不是都不满足，所以如果同一元素的两个点在一个 scc 中，一定无解
-
拓扑排序值越大则约有可能
那肯定有 聪明的小朋友们 发现了，这样模拟上面的图，答案是 1 1 1 1，这也不对，答案是这个图画错了
我们知道如果：
\[
p \Rightarrow q
\]
则称 \(p\) 为 \(q\) 的充分条件，\(q\) 为 \(p\) 的必要条件，因而满足：
\[
\neg q \Rightarrow \neg p
\]
所以我们把这样的几条边连上：
就只有两个 scc 了，我们显然要满足上面的，及答案为 1011。
所以我们不仅要连正边，也要连反边。
CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 | #include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=4e6+5,M=4e6+5;
int n,m;
int ins[N];
int st[N],top;
int cnt,edcc[N];
int idx,dfn[N],low[N];
int tot=1,head[N],ver[M<<1],nxt[M<<1];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void add(int a,int b){
ver[++tot]=b;
nxt[tot]=head[a],head[a]=tot;
}
void Tarjan(int x){
dfn[x]=low[x]=++idx;
st[++top]=x,ins[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int y;cnt++;
do{
y=st[top--];
edcc[y]=cnt;
ins[y]=0;
}while(y!=x);
}
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
cin>>n>>m;
while(m--){
int i,a,b,j;
cin>>a>>i>>b>>j;
add(a+(n*i),b+(n*j));
add(b+(n*(j^1)),a+(n*(i^1)));
}
for(int i=1;i<=2*n;i++)
if(!dfn[i])
Tarjan(i);
for(int i=1;i<=n;i++)
if(edcc[i]==edcc[i+n]){
cout<<"IMPOSSIBLE";
return 0;
}
cout<<"POSSIBLE\n";
for(int i=1;i<=n;i++) cout<<(edcc[i]>edcc[i+n])<<' ';
return 0;
}
/*这个代码并非 P4782【模板】2-SAT*/
|
扩展
一般的题问你是否有解，或者有 SPJ。
如果需要你判断不确定，就需要用上面的判断是否在一条链上，否则不知道：
扩展 CODE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 | #include<bits/stdc++.h>
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
const int N=4005,M=10005;
int n,m;
int d[N];
int vis[N];
int dis[N];
int ins[N];
int st[N],top;
int cnt,scc[N];
int idx,dfn[N],low[N];
int tot,head[N],ver[M<<1],nxt[M<<1];
vector<int> v[N];
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
void add(int a,int b){
ver[++tot]=b;
nxt[tot]=head[a],head[a]=tot;
}
void Tarjan(int x){
dfn[x]=low[x]=++idx;
st[++top]=x,ins[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int y;cnt++;
do{
y=st[top--];
scc[y]=cnt;
ins[y]=0;
}while(y!=x);
}
}
void dfs(int x,int fa){
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(vis[y]) continue;
dfs(y,x);
}
}
bool check(int x){
memset(vis,0,sizeof vis);
dfs(x,0);
for(int i=1;i<=n;i++)
if(vis[i]&&vis[i+n])
return 0;
return 1;
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;char c,d;
cin>>a>>c>>b>>d;
int p1=(c=='Y'),p2=(d=='Y');
add(a+n*(p1^1),b+n*p2);
add(b+n*(p2^1),a+n*p1);
}
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]){
cout<<"IMPOSSIBLE";
return 0;
}
for(int x=1;x<=2*n;x++){
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(scc[x]==scc[y]) continue;
v[scc[x]].push_back(scc[y]);
d[scc[y]]=0;
}
}
for(int i=1;i<=n;i++){
if(check(i)&&check(i+n)) cout<<'?';
else if(scc[i]<scc[i+n]) cout<<'N';
else cout<<'Y';
}
return 0;
}
|
注意会退化为 \(\mathcal O(N^2)\)