poj 3905 Perfect Election（2-SAT判断简单）-白红宇

poj 3905 Perfect Election（2-SAT判断简单）

阅读量：4073 次

发布时间：2019-05-25

本文共 1279 字，大约阅读时间需要 4 分钟。

【题目链接】

【思路】

2-SAT简单的判断题

【代码】

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int MAXN = 1010;const int VN   = MAXN*2;const int EN   = VN*VN*2;int n, m; struct Edge{    int v, next;};struct Graph{    int size, head[VN];    Edge E[EN];    void init(){size=0; memset(head, -1, sizeof(head)); };    void addEdge(int u, int v){        E[size].v = v;        E[size].next = head[u];        head[u] = size++;    }}g;class Two_Sat{public:    bool check(const Graph& g, const int n){        scc(g, 2*n);        for(int i=0; i
       
        0 && b>0){ // + +                --a; --b;                g.addEdge(a+n, b);                g.addEdge(b+n, a);            }else if(a>0 && b<0){ // + -                b = -b;                  --a; --b;                g.addEdge(a+n, b+n);                g.addEdge(b, a);            }else if(a<0 && b>0){ // - +                a = -a;                --a; --b;                g.addEdge(a, b);                 g.addEdge(b+n, a+n);            }else if(a<0 && b<0){// - -                a = -a; b = -b;                --a; --b;                g.addEdge(a, b+n);                g.addEdge(b, a+n);            }        }        if(sat.check(g, n)) puts("1");        else puts("0");        }    return 0;}