我的第二次 2-SAT 练习
题目
https://codeforces.com/contest/1697/problem/F
给你m个限制, 分别可能是
- $a_i \neq x$
- $a_i+a_j \ge x$
- $a_i+a_j \le x$
请构造一个满足限制的长n的数组a, 且每个元素在$[1,k]$之间
范围
n 2e4
m 2e4
k 10
2s
512MB
题解
我的思路
一眼2-sat,写过但不熟, 来看看题解如何建立图的
tourist ,jiangly也是拖的板子, XD, 看来我要好好准备板子了?
题解
一个值拆成2k个点
分别是$\le 1,\le 2,\cdots,\le k,>1,>2,\cdots,>k$
其中$\le i, > i$ 是一个互补对
$(i,v,0) = a_i \le v$
$(i,v,1) = a_i > v$
因为2-sat 就是每个点选或不选 0/1, 而上面的两个必定一个满足一个不满足
$(i,v,0) \to (i,v+1,0)$ 不等式关系
$(i,v,1) \to (i,v-1,1)$ 不等式关系 (可以由上面自动建立对称关系
$(i,v,1) \to (i+1,v,1)$ 非严格单增
$(i,x,0) \to (i,x-1,0)$, $a_i \ne x$
$(i,x-1,1) \to (i,x,1)$, $a_i \ne x$ (可以由上面自动建立对称关系
$(i,v,1) \to (j,x-a_i-1,0)$, $a_i + a_j \le x$, 轮换$i,j$
$(i,v,0) \to (j,x-a_i-1,1)$, $a_i + a_j \ge x$, 轮换$i,j$
对于限制必定不合法的$(i,v,x)$ , 建立 $(i,v,x) \to (i,v,x\oplus 1)$
2-sat 的选择
之前有个问题, 我一直没想太通, 现在有点思路了
假设我们完成建边和tarjan的部分
如下, 这样那怎么顺序选都没问题
而对于这种, 你是不能去选b1/c1 的,而这也是Tarjan 不会处理的,因为tarjan只是合并联通块, 这种还算有答案
1
2
3
| a0 <-> b0
b1 <-> c1
c1 -> a0
|
这种是没有答案, 而且tarjan 的时候是判断不了的
那么两个办法我想的
方法一
如果我们要加 $a[x] \to b[y]$
考虑 如果 $b[y\oplus 1]$ ,那么a不能选x, 所以同时会产生$b[y\oplus 1] \to a[x\oplus1]$
这个好处是,本身可以利用tarjan
方法二
在tarjan处理完scc后, 对scc的每个点的反点做并查集, 缺点是还要跑并查集
等价性 一个奇怪的视角可以证明就是 这些操作是对称性的, 比如方法一里面每次都是对称加的边, 而方法二,不妨设scc 中的反点个数比它大,那么scc必定会合其它scc连接,最终所有并查集完成后, scc和scc反点的scc个数相等
这两个任选一种以后, 最后对scc/并查集 做原图的反向边 做倒序拓扑选择,必定有解?
再看上面的 3个例子
第一个不变
第二个变成如下,你需要反向拓扑选择
1
2
3
| a0 <-> b0 <-> c0
a1 <-> b1 <-> c1
c1 -> a0
|
第三个则全部连到一个并查集里了, 直接确定不合法了
第三个是限制的不可选状态
比如 $(i,x)$ 不可选, 之前的办法是做一个 失败的节点,让它和这个节点双向连通
而现在发现其实$(i,x) \to (i,x\oplus 1)$, 因为这样如果选$(i,x)$自动造成矛盾
注意区别是不可选还是选了一定满足
代码
我先自己写了个twosat的板子,下次也可以用
https://codeforces.com/contest/1697/submission/160657743
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
ll read(){ll r;scanf("%lld",&r);return r;}
class TwoSat{
vector<int> low;
vector<int> dfn;
stack<int> stk;
vector<int> res;
vector<vector<int> > p;
int n;
void scc(int v) {
static int id = 0;
low[v] = dfn[v] = id++;
stk.push(v);
for(auto w:p[v]){
if(dfn[w] == -1){
scc(w);
low[v] = min(low[v],low[w]);
} else if(res[w] == -1){
low[v] = min(low[v],dfn[w]);
}
}
int u;
if(low[v] == dfn[v]) {
do{
res[u = stk.top()] = v;
stk.pop();
}while(u != v);
}
}
public:
TwoSat(int SZ):n(SZ){
low = vector<int>(2*n,-1);
dfn = vector<int>(2*n,-1);
stk = {};
res = vector<int> (2*n,-1);
p = vector<vector<int> >(2*n);
}
bool calc(vector<bool> & ans){
rep(i,0,2*n) if(res[i] == -1) scc(i);
rep(i,0,n) if(res[i*2] == res[i*2+1]) return false;
vector<int> revscc(2*n);
rep(i,0,n) {
revscc[res[i*2]] = res[i*2+1];
revscc[res[i*2+1]] = res[i*2];
}
vector<set<int> > scc2scc(2*n);
unordered_map<int,int> degree;
unordered_map<int,bool> scctf;
rep(i,0,2*n) {
degree[res[i]] = 0;
for(auto j:p[i]){
if(res[i] == res[j]) continue;
scc2scc[res[j]].insert(res[i]);
}
}
for(auto s:scc2scc){
for(auto t:s) degree[t]++;
}
vector<int> d0;
for(auto [v,d]: degree) if(!d) d0.pb(v);
rep(i,0,d0.size()) {
if(!scctf.count(d0[i])){
scctf[d0[i]] = true;
scctf[revscc[d0[i]]] = false;
}
for(auto item:scc2scc[d0[i]]) {
if(!(--degree[item])) d0.pb(item);
}
}
ans = vector<bool>(n);
rep(i,0,n) ans[i] = scctf[res[i*2+1]];
return true;
}
void p2(pair<int,bool> pi, pair<int,bool> pj){
auto [i,bi] = pi;
auto [j,bj] = pj;
assert(i >= 0 && i < n);
assert(j >= 0 && j < n);
p[2*i+bi].pb(2*j+bj);
p[2*j+(!bj)].pb(2*i+(!bi));
}
};
int n;
int m;
int k;
int c(int i,int j){
return i*k+j;
}
void w(){
n = read();
m = read();
k = read();
TwoSat ts(n*k);
rep(i,0,n){
rep(j,0,k-1){
ts.p2({c(i,j),0},{c(i,j+1),0});
}
ts.p2({c(i,k-1),1},{c(i,k-1),0});
}
rep(i,0,n-1){
rep(j,0,k){
ts.p2({c(i,j),1},{c(i+1,j),1});
}
}
while(m--){
int op = read();
int i = read()-1;
if(op == 1){
int x = read()-1;
if(x){
ts.p2({c(i,x),0},{c(i,x-1),0});
}else{
ts.p2({c(i,x),0},{c(i,x),1});
}
}else if(op == 2){
int j = read() - 1;
int x = read();
rep(v,1,k+1){
int v2 = x - v - 1;
if(v2 >= 1 && v2 <= k){
ts.p2({c(i,v-1),1},{c(j,v2-1),0});
}else if(v2<1){
ts.p2({c(i,v-1),1},{c(i,v-1),0});
ts.p2({c(j,v-1),1},{c(j,v-1),0});
}
}
}else if(op == 3){
int j = read() - 1;
int x = read();
rep(v,1,k+1){
int v2 = x - v - 1;
if(v2 >= 1 && v2 <= k){
ts.p2({c(i,v-1),0},{c(j,v2-1),1});
}else if(v2 > k){
ts.p2({c(i,v-1),0},{c(i,v-1),1});
ts.p2({c(j,v-1),0},{c(j,v-1),1});
}
}
}
}
vector<bool> ans;
vector<int> a(n);
if(!ts.calc(ans)){
printf("-1\n");
}else{
rep(i,0,n){
rep(j,0,k){
if(!ans[i*k+j]){
a[i] = j+1;
break;
}
}
}
rep(i,0,n) printf("%d%c",a[i]," \n"[i==n-1]);
}
}
int main(){
int t = read();
while(t--) w();
return 0;
}
|
总结
这里的问题就是说 选则一个范围的值,怎么变成2-sat需要的 真/假
这里的办法是拆成大于小于
当然从逻辑上 用 $= v$ 和$\ne v$ 也可以, 但是这样的问题是, 在做上面的和的不等式的关系时, 边的量就很大了, 不是k条边了
之前2-sat 还有点问题,缺少了一些反向的连接,和缩点后的反向拓扑序选择
准备准备2sat的板子了
参考
官方