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//這里標(biāo)號從0開始 { vector<int> G[MAXN*2];//鄰接表 bool mark[MAXN*2];//每個點是否被標(biāo)記 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;//對應(yīng)點被標(biāo)記，不符合要求 if (mark[x]) return true;//已經(jīng)被標(biāo)記直接返回 mark[x] = true;//標(biāo)記 for (int i=0;i<G[x].size();i++)//繼續(xù)標(biāo)記 { 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) {新聞熱點
疑難解答
