BZOJ傳送門 經典2-SAT模型，注意輸入 (慶祝blog第200篇博文)
#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define ms(i,j) memset(i,j, sizeof i); using namespace std;const int MAXN = 100 + 5;struct twoSAT{ bool mark[MAXN*2]; vector<int> G[MAXN*2]; int n; int c, S[MAXN*2]; void init(int ni) { n = ni; for (int i=0;i<2*n;i++) G[i].clear(); ms(mark, false); } bool dfs(int x) { if (mark[x^1]) return false; if (mark[x]) return true; mark[x] = true; S[++c] = x; for (int i=0;i<G[x].size();i++) if (!dfs(G[x][i])) return false; return true; } void addE(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);//2x for man, 2x+1 for han } bool solve() { for (int i=0;i<2*n;i+=2) if (!mark[i] && !mark[i+1]) { c = 0; if (!dfs(i)) { for (int j=1;j<=c;j++) mark[S[j]] = false; c = 0; if (!dfs(i+1)) return false; } } return true; }}ts;int k;int n,m;int getss(){ char ans; while (true) { ans = getchar(); if (ans=='m') return 0; if (ans=='h') return 1; int ret = 0; while (ans>='0'&&ans<='9') { ret = ret*10+ans-'0'; ans = getchar(); } if (ret>0) return ret; }}void inpu(){ int v1 = getss(); int z1 = getss(); int v2 = getss(); int z2 = getss(); ts.addE(z1-1, z2-1, v1, v2);}int main() { scanf("%d", &k); while (k--) { scanf("%d%d", &n,&m); ts.init(n); for (int i=0;i<m;i++) { inpu(); } if (ts.solve()) {新聞熱點
疑難解答
