2-sat 问题:
给定 $n$ 个二元组 $(A,B)$, 你需要从这些二元组中选取 $n$ 个元素, 每个二元组中必须恰好选择一个元素.
同时给出 $m$ 个约束条件, 每个条件形如 "选 A 必须选 B","选 A 就不能选 B" 等. 求一种合法的选取方案.
思路:
暴力 $O(2^n\times m)$ 多好啊.
考虑将所有约束条件转化成 "选 A 必须选 B" 这种类型.
建立一个有 $2\times n$ 个节点的图, 对于每个条件我们连一条 $A\rightarrow B$ 的有向边.
此时这张图满足一些性质:
如果存在一个二元组 $(A,B)$, 使得 A 可达 B 且 B 可达 A(即 A,B 在同一个强连通分量中), 那么肯定无解. 若不存在这样的二元组那么一定有解.
若一个点被选入答案序列, 那么这个点所有的可达节点都必须被选入.
若一个点确定不被选入答案序列, 那么所有可达这个点的节点都不能被选入.
基于后两个性质, 我们考虑先将原图缩点 (保证无环). 然后建立原图的反图.
按照反图的拓扑序依次选择节点并标记为选, 同时将与该节点在同一二元组内的点标记为不选, 将不选标记沿着路径传递.
该方法的证明见此: 赵爽《2-SAT 解法浅析》.
模板题目: loj10097 https://loj.ac/problem/10097
- #include<algorithm>
- #include<iostream>
- #include<cstring>
- #include<cstdio>
- #include<stack>
- using namespace std;
- #define MAXN 100005
- #define MAXM 500005
- #define INF 0x7fffffff
- #define ll long long
- inline int read(){
- int x=0,f=1;
- char c=getchar();
- for(;!isdigit(c);c=getchar())
- if(c=='-')
- f=-1;
- for(;isdigit(c);c=getchar())
- x=x*10+c-'0';
- return x*f;
- }
- int N,M,hd[MAXN],to[MAXM],nxt[MAXM],cnt;
- int dfn[MAXN],low[MAXN],cl[MAXN],tot,num;
- bool vis[MAXN]; stack<int> s;
- inline void addedge(int u,int v) {to[++cnt]=v,nxt[cnt]=hd[u],hd[u]=cnt;}
- inline void tarjan(int u){
- dfn[u]=low[u]=++num;
- vis[u]=1;s.push(u);
- for(int i=hd[u];i;i=nxt[i]){
- int v=to[i];
- if(!dfn[v])
- tarjan(v),low[u]=min(low[u],low[v]);
- else if(vis[v])
- low[u]=min(low[u],dfn[v]);
- }
- if(dfn[u]==low[u]){
- tot++;
- while(s.top()!=u){
- cl[s.top()]=tot;
- vis[s.top()]=0;
- s.pop();
- }
- cl[s.top()]=tot;
- vis[s.top()]=0;
- s.pop();
- }
- }
- int main(){
- N=read()<<1,M=read();
- for(int i=1;i<=M;i++){
- int u=read(),v=read();
- addedge(u,(v&1)?v+1:v-1);
- addedge(v,(u&1)?u+1:u-1);
- }
- for(int i=1;i<=N;i++)
- if(!dfn[i])
- tarjan(i);
- for(int i=1;i<=N;i+=2)
- if(cl[i]==cl[i+1]){
- printf("NIE\n");
- return 0;
- }
- for(int i=1;i<=N;i+=2)
- if(cl[i]<cl[i+1]) printf("%d\n",i);
- else printf("%d\n",i+1);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2970066.html