|算法讨论|2-SAT 学习笔记

2019-11-14 09:12:40

字体：大中小

来源：转载

供稿：网友

2-SAT模板题：BZOJ 2199[Usaco2011 Jan]奶牛议会

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define ms(i,j) memset(i,j, sizeof i); using namespace std; const int MAXN = 1000 + 5;const char orz[10] = {'Y', 'N', '?'};int n,m; int ans[MAXN];struct twoSAT//这里标号从0开始 { vector<int> G[MAXN*2];//邻接表 bool mark[MAXN*2];//每个点是否被标记 int n; int init(int ni)//初始化 { n = ni; for (int i=0;i<2*n;i++) G[i].clear(); } int addEdge(int x, int y, int xv, int yv)//加一个条件 { x = x*2+xv; y = y*2+yv; G[x^1].push_back(y); G[y^1].push_back(x);//2i是假，2i+1是真 } int dfs(int x) { if (mark[x^1]) return false;//对应点被标记，不符合要求 if (mark[x]) return true;//已经被标记直接返回 mark[x] = true;//标记 for (int i=0;i<G[x].size();i++)//继续标记 { if (!dfs(G[x][i])) return false; } return true; } int check(int x)//检查一个议案是否通过 { ms(mark, false); return dfs(x); }}ts;int main() { scanf("%d%d", &n,&m); ts.init(n); for (int i=0;i<m;i++) { int bi,ci; char vbi,vci; scanf("%d %c %d %c", &bi,&vbi,&ci,&vci); int vvbi = false, vvci = false; if (vbi=='Y') vvbi = true; if (vci=='Y') vvci = true; ts.addEdge(bi-1,ci-1,vvbi,vvci); } for (int i=0;i<n;i++) { int p = ts.check(i*2); int q = ts.check(i*2+1); if (!p&&!q) {PRintf("IMPOSSIBLE"); return 0;} if (p&&q) ans[i] = 2; else if (!p) ans[i] = 0; else ans[i] = 1; } for (int i=0;i<n;i++) putchar(orz[ans[i]]); return 0; }

上一篇：LeetCode 70. Climbing Stairs

下一篇：java之pdf转jpg图片