題目鏈接：http://poj.org/problem?id=3207

#include <cstdio> #include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <queue> #include <vector>#define maxn 1050 #define maxe 550 #define INF 0x3f3f3f using namespace std;struct TwoSat{int n;vector<int> G[maxe*2];bool mark[maxe*2];int s[maxe*2],cnt;void init(int n){this->n = n;memset(mark,0,sizeof(mark));for(int i=0;i<=n*2;i++) G[i].clear();}bool dfs(int u){if(mark[u^1]) return false;if(mark[u]) return true;mark[u] = true;s[cnt++] = u;for(int i=0;i<G[u].size();i++){if(!dfs(G[u][i])) return false;}return true;}void add_clause(int u,int uval,int v,int vval){u = u*2 + uval;v = v*2 + vval;G[u^1].push_back(v);G[v].push_back(u^1);G[v^1].push_back(u);G[u].push_back(v^1);}bool solve(){for(int i=0;i<n*2;i+=2){ if(!mark[i] && !mark[i+1]){ cnt = 0; //這就是一直WA的原因 if(!dfs(i)){while(cnt > 0) mark[s[--cnt]] = false;if(!dfs(i+1)) return false; }}}return true; //這也是WA的原因 } }solver;int main() {//freopen("input.txt","r",stdin);int n,m;scanf("%d%d",&n,&m);struct Edge{int u,v;}e[maxe];for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);if(a > b){int temp = a;a = b;b = temp;} e[i].u = a; e[i].v = b;}solver.init(m);for(int i=0;i<m;i++)for(int j=i+1;j<m;j++){int x1 = e[i].u ,y1 = e[i].v;int x2 = e[j].u ,y2 = e[j].v;if((x2>x1 && x2<y1 && y2 > y1) ||(y2>x1 && y2<y1 && x2<x1)){solver.add_clause(i,1,j,1); }}if(solver.solve()) printf("panda is telling the truth...\n");else printf("the evil panda is lying again\n"); } View Code

?

轉載于:https://www.cnblogs.com/acmdeweilai/p/3235873.html

總結

以上是生活随笔為你收集整理的poj 3207 2-sat的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。