分享一篇不錯的2-sat介紹博客
2-SAT可以用來判斷給出的限制能不能全滿足。 那么枚舉每個議案，用2-SAT分別判斷當這個議案通過和否決時有沒有解。 在判斷的時候因為已經知道的當前議案的通過情況，只用從對應的點dfs出去，標記路徑上的點，最后判定有沒有矛盾。
#include <cstdio>#include <cstring>#include <string>#include <iostream>#define N 2010#define M 8010using namespace std;int n,m,x,y,cnt;int G[N],V[N];char a,b,Ans[N];struct edge{ int t,nx;}E[M];inline void reaD(int &x){ char Ch=getchar();x=0; for(;Ch>'9'||Ch<'0';Ch=getchar()); for(;Ch>='0'&&Ch<='9';x=x*10+Ch-'0',Ch=getchar());}inline void reaD(char &x){ while((x=getchar())!='Y'&&x!='N');}void InserT(int x,int y){ E[++cnt].t=y;E[cnt].nx=G[x];G[x]=cnt;}void dfs(int x){ V[x]=1; for(int i=G[x];i;i=E[i].nx) if(!V[E[i].t]) dfs(E[i].t);}int check(int x){ memset(V,0,sizeof(V)); dfs(x); for(int i=1;i<=n;i++) if(V[i<<1]&&V[i<<1|1]) return 0; return 1;}int main(){ reaD(n);reaD(m); for(int i=1;i<=m;i++){ reaD(x);reaD(a);reaD(y);reaD(b); if(a=='Y') x=x<<1|1; else x=x<<1; if(b=='Y') y=y<<1|1; else y=y<<1; InserT(x,y^1);InserT(y,x^1); } for(int i=1;i<=n;i++){ int yes=check(i<<1),no=check(i<<1|1); if(yes&&no) Ans[i]='?'; else if(!yes&&!no) {puts("IMPOSSIBLE");return 0;} else if(yes) Ans[i]='Y'; else Ans[i]='N'; } return puts(Ans+1),0;}新聞熱點
疑難解答
