2-sat 吧。。。。
其实我jio得它一点都不难
嗯
2-sat是个啥东西呢？
其实就是有很多人，他们每个人有两个要求，一个要求可以说是要求一个数为0或1
而对于第i个数，我们可以选择为0或为1
最终询问是否可以满足全部人的要求
（我讲了个啥啊）
emmmm
其实我一看就大概懂了。。。
这不就是约束的变形吗。。。
之间建图判断个连通性就好了啊。。。
这不是模板题吗。。。
其实确实很简单。。。
（还不如说是我上了一节tarjan课 ）（逃）
其实吧。。。
这个还真的是（省选）T1的难度。。。awa
主要是以为这个很好就可以看出来是这种问题。。。
进入正题。
对于这种问题，建图是显而易见的吧。
既然2-sat问题能够被单独列出来，肯定也是有原因的。
2sat其实妙就妙在他的建图上。
对于一个人，我们如果要满足他的条件a，b如果我们不满足a,那么就一定要满足b如果我们不满足b,那么就一定要满足a
于是我们就把这个问题从“或者”，转化为了“一定”
而这就是一个很明显的约束条件了。
即为边(a,!b)和(b,!a);
这其实就是如果不满足b时就一定要满足a
如果不满足a时就一定要满足b
然后，图就建好了
是不是很好理解？（其实我老师讲的时候我觉得很好，为什么我讲就不一样了啊淦）
这里给一份建图的代码。
n=read();m=read(); for(int i=1;i<=m;i++) { a=read();va=read(); b=read();vb=read(); if(va&&vb) { add(a,b+n); add(b,a+n); } else if(!va&&vb) { add(a+n,b+n); add(b,a); } else if(va&&!vb) { add(b+n,a+n); add(a,b); } else if(!va&&!vb) { add(b+n,a); add(a+n,b); } }
简单易懂
awa
这个其实就是整个2-sat最精髓的部分了。
剩下的就是tarjan
对于我们建的图，选择的点一定不能同时有一个点以及他的负点。
一旦选择了，就什么这个情况是无解的。
tarjan判断是否在同一个强联通分量里就好了。
但是如果题目要求字典序，就是另一个故事了。
那么只能暴力。
虽然说吧。。。
暴力的时间复杂度也是很优秀的了吧。。。
可是它能被卡掉。
一个链就炸了。
这里我放上全部的代码，是tarjan的
#include<bits/stdc++.h> #define ll long long using namespace std; int head[4000001],tot,n,m,a,b,va,vb,dfsc,ccs,color[2000001],dfn[2000001],low[2000001];bool vis[2000001]; stack<int> stk; struct edge { int next,to; }e[4000001]; inline ll read() { char c=getchar();ll a=0,b=1; for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1; for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48; return a*b; } void add(int i,int j) { e[++tot].next=head[i]; e[tot].to=j; head[i]=tot; } void tarjan(int x,int fa) { dfn[x]=low[x]=++dfsc; stk.push(x);vis[x]=true; for(int i=head[x];i!=0;i=e[i].next) { int u=e[i].to; if(u==fa)continue; if(!dfn[u]) { tarjan(u,x); low[x]=min(low[x],low[u]); } else if(vis[u])//有一条返祖边，要更新 { low[x]=min(low[x],dfn[u]); } } if(dfn[x]==low[x])//有一个强联通分量 { ++ccs; do { color[x]=ccs; x=stk.top();stk.pop();vis[x]=false; } while(dfn[x]!=low[x]); } } int main() { freopen("2sat.in","r",stdin); freopen("2sat.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++) { a=read();va=read(); b=read();vb=read(); if(va&&vb) { add(a,b+n); add(b,a+n); } else if(!va&&vb) { add(a+n,b+n); add(b,a); } else if(va&&!vb) { add(b+n,a+n); add(a,b); } else if(!va&&!vb) { add(b+n,a); add(a+n,b); } } for(int i=1;i<=n*2;i++) { if(dfn[i]==0) { tarjan(i,0); } } for(int i=1;i<=n;i++) { if(color[i]==color[i+n]) { puts("IMPOSSIBLE"); return 0; } } puts("POSSIBLE"); for(int i=1;i<=n;i++) { cout<< (color[i]>color[i+n]) <<' '; } return 0; }
