厦门做网站哪家好,百度站长平台论坛,龙岩网站建设一般多少钱, pp下载安装 app文章目录前言实现代码所谓2-SAT#xff0c;就是解决两个SAT的问题 #xff08;逃#xff09;
前言 SAT 是适定性#xff08;Satisfiability#xff09;问题的简称。一般形式为 k - 适定性问题#xff0c;简称 k-SAT。而当 k2 时该问题为 NP 完全的。所以我们只研究 …
文章目录前言实现代码所谓2-SAT就是解决两个SAT的问题 逃
前言 SAT 是适定性Satisfiability问题的简称。一般形式为 k - 适定性问题简称 k-SAT。而当 k2 时该问题为 NP 完全的。所以我们只研究 k2 的情况。 2-SAT简单的说就是给出 k 个集合每个集合有两个元素已知若干个 (a,b)表示 a 与 b 矛盾其中 a 与 b 属于不同的集合。然后从每个集合选择一个元素判断能否一共选 n 个两两不矛盾的元素。显然可能有多种选择方案一般题中只需要求出一种即可。 感觉2-SAT也就是听起来高大上 理解和代码实现其实都不难 题目很多也都很板 不明白为什么这是个模板就紫的算法 这不比网络流、平衡树之类的阳间多了
实现
考虑建图tarjan缩点 然后判断若a与a’同属于一个分量则矛盾 否则构造方案选tarjan染色编号小的那个点 这利用了tarjan栈的性质相当于反的拓扑序 一个讲的很清楚的地方
代码
洛谷模板传送门
#includebits/stdc.h
using namespace std;
#define ll long long
const int N4e6100;
const int mod998244353;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m;
int id[N][2];
struct node{int to,nxt;
}p[N];
int fi[N],cnt-1;
void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
int dfn[N],low[N],tim,zhan[N],col[N],tot,top;
void tarjan(int x){dfn[x]low[x]tim;zhan[top]x;for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(!dfn[to]){tarjan(to);low[x]min(low[x],low[to]);}else if(!col[to]) low[x]min(low[x],dfn[to]);}if(dfn[x]low[x]){col[x]tot;while(zhan[top]!x){col[zhan[top--]]tot;}top--;}
}
int main(){memset(fi,-1,sizeof(fi));nread();mread();for(int i1;in;i){id[i][0]i;id[i][1]in;}tot2*n;for(int o1;om;o){int iread(),aread(),jread(),bread();addline(id[i][!a],id[j][b]);addline(id[j][!b],id[i][a]);}for(int i1;i2*n;i){if(!dfn[i]) tarjan(i);}for(int i1;in;i){if(col[i]col[in]){printf(IMPOSSIBLE\n);return 0;}}printf(POSSIBLE\n);for(int i1;in;i){printf(%d ,col[i]col[in]);}
}
/*
4
1 2 3 4
*/
