[BZOJ2199][Usaco2011 Jan][2-SAT]奶牛议会

2019-11-11 05:52:45

字体：大中小

来源：转载

供稿：网友

分享一篇不错的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;}

上一篇：中文Url编码

下一篇：oj中用到的一些数学上的算法