学习目标：
2-SAT(小结)
这个人讲的很好，我就不详细讲了
学习内容：
注意点
1.适用范围：x1&x2=0,问给出 m 个关系表达式后，能否给这 n 个变量找出一个赋值的方法，使得满足所有的表达式；
2.对于每个变量都只有两种取值：0 / 1，那么对于每个点，我们把每个变量拆成 true 点和 false 点；
3.要注意只有关系明确的时候才能建边； 其中一个不成立则另一个一定成立（这是明确的关系）；
4.无解的情况：某一个变量的 false 能走到 true，从 true 也能走到 false，也就是说，某一个变量的两个取值在同一个强连通分量内的话，就说明无解。
5.输出解集的时候，我们要注意，tarjan给连通分量标号的拓扑序是反序，拓扑序越大，扑序越大的点其所在强联通分量编号越小，我们选择编号小的就行了。
6.至于输出字典序最小的解集，就要O(n*m)爆搜了。
学习例题：
学习产出：
感觉都挺水的，不知道是题目水还是数据水，放俩板子搁这吧。
拓扑序任意解：O（n+m）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+6;
const int mod=1e9+7;
vector<int>G[N];
stack<int>s;
int n,m,x,y,a,b,tot,colnum;
int dfn[N],col[N],vis[N],low[N];
void tarjan(int u) {
dfn[u]=low[u]=++tot;
vis[u]=1,s.push(u);
for(auto v:G[u]) {
if(!dfn[v])
tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
++colnum;
while(true) {
int v=s.top();
s.pop();
vis[v]=0,col[v]=colnum;
if(u==v)break;
}
}
}
void add(int u,int v) {
G[u].push_back(v);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
scanf("%d%d%d%d",&a,&x,&b,&y);
if(x==0&&y==0) {
add(a+n,b);
add(b+n,a);
} else if(x==0&&y==1) {
add(b,a);
add(a+n,b+n);
} else if(x==1&&y==0) {
add(b+n,a+n);
add(a,b);
} else if(x==1&&y==1) {
add(b,a+n);
add(a,b+n);
}
}
for(int i=1; i<=n*2; i++) {
if(!dfn[i])tarjan(i);
}
for(int i=1; i<=n; i++) {
if(col[i]==col[i+n]) {
printf("IMPOSSIBLE\n");
return 0;
}
}
printf("POSSIBLE\n");
for(int i=1; i<=n; i++) {
if(col[i]<col[i+n])printf("0 ");
else printf("1 ");
}
printf("\n");
}
字典序最小解：O（n*m）复杂度有些玄学
#include<bits/stdc++.h>
using namespace std;
const int maxn = 8006;
int n, m, stak[maxn], top, col[maxn<<1];
vector<int> G[maxn<<1];
int mir(int x) {
return x&1? x+1: x-1;
}
bool paint(int x) {
if(col[x])
return col[x] == 1;
col[x] = 1;
col[mir(x)] = 2;
stak[++top] = x;
for(unsigned int i = 0; i < G[x].size(); ++i) {
int id = G[x][i];
if(!paint(id))
return 0;
}
return 1;
}
bool work() {
for(int i = 1; i <= (n<<1); ++i)
if(!col[i]) {
top = 0;
if(!paint(i)) {
while(top) col[stak[top]] = col[mir(stak[top])] = 0, top--;
if(!paint(mir(i)))
return 0;
}
}
return 1;
}
int main() {
while(scanf("%d%d", &n, &m) != EOF) {
for(int i = 1; i <= m; ++i) {
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(mir(y));
G[y].push_back(mir(x));
}
if(work()) {
for(int i = 1; i <= (n<<1); ++i)
if(col[i] == 1)
printf("%d\n", i);
} else
printf("NIE\n");
for(int i = 1; i <= (n<<1); ++i)
G[i].clear(), col[i] = 0;
}
}
文章评论