分享一篇不錯(cuò)的2-sat介紹博客
2-SAT可以用來(lái)判斷給出的限制能不能全滿足。 那么枚舉每個(gè)議案，用2-SAT分別判斷當(dāng)這個(gè)議案通過和否決時(shí)有沒有解。 在判斷的時(shí)候因?yàn)橐呀?jīng)知道的當(dāng)前議案的通過情況，只用從對(duì)應(yīng)的點(diǎn)dfs出去，標(biāo)記路徑上的點(diǎn)，最后判定有沒有矛盾。
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
