POJ_3678 Katu Puzzle 2-sat

http://poj.org/problem?id=3678

題意：給你一個有N個點的圖，和其中的某一些邊，每條邊都可以記為：（a,b,c,d），其中a，b代表的是邊所依附的兩個結點，d表示的是一種運算符，0: AND , 1 :OR , 2:XOR，c表示a,b頂點的值運用d運算符之後的結果應為c。需要給每個結點都賦一個值，使得滿足所有的限制條件。

思路：2-sat問題，首先我們可以看出，所有的運算都是bool運算，是以每個結點的值要不是0，就是1，隻有兩種選擇，這就是典型的2-sat問題，而且隻要判定是否存在這樣的結點值的配置設定就可以了，屬于2-sat中的判定問題。然後我們就需要考慮建圖，對于每個結點i，如果它取值為0 ，則表示選擇了2*i-1号結點，如果取值為1，則表示選擇了2*i号結點。這樣我們就可以根據每個結點的出邊來建圖了，具體規則如下：

a && b = 1 : 2*a -> 2*b (兩個都選擇1)  ,  2*a-1->2*a（a号結點選0的話，無論b選什麼都不會成立，所有這裡就添加一條沖突的邊，表示如果結點a選擇0，則結點1也就要選擇1，這裡在最後的圖中2*a和2*a-1就會在同一個強連通分量當中，具體的證明可以用2-sat中邊的對稱性來證明。）

a && b = 0 : 2*a -> 2*b-1 

a || b = 1 :  2*a-1 -> 2*b ;

a || b = 0 : 2*a-1 -> 2*b-1 ;   2*a -> 2*a-1 ;

a ^ b = 1 : 2*a ->2*b-1 ;  2*a-1 -> 2*b 

a ^ b = 0 : 2*a -> 2*b  ;  2*a - 1 -> 2 *b -1 

上述的所有邊都沒有考慮對稱的那條，這是因為原本建的圖就是雙向的，對稱的那條邊在下次搜尋的時候自然會搜尋到。

代碼：

#include<stdio.h>
#include<string.h>
int N ,M ;
const int MAXE = 1000010 ;

struct Node{
    int num , next ,flag ,val;
}edge[MAXE*2] ;
int root[1010] , ec ;

struct Node1{
    int num, next ;
}ex[1000*1000] ;
int r[1010] , ee ;
int rr[1010*2] ;

void init(){
    memset(root, -1, sizeof(root));
    ec = 0 ;
    memset(r, -1, sizeof(r));
    ee = 0 ;
}

void add(int a,int b , int c, int d){
    edge[ec].num = b ;
    edge[ec].next = root[a] ;
    edge[ec].flag = d ;
    edge[ec].val = c ;
    root[a] = ec++ ;
}

void add2(int a,int b){
    ex[ee].num = b ;
    ex[ee].next = r[a] ;
    r[a] = ee++ ;
}
const int MAXN = 1010*2 ;
int dfn[MAXN] , low[MAXN] , stack[MAXN] ,col[MAXN];
bool in[MAXN] ;
int top,idx, Bcnt ;

void tarjin(int u){
    int v ;
    low[u] = dfn[u] = ++idx ;
    stack[++top] = u ; in[u] =1 ;
    for(int i=r[u] ;i!=-1;i=ex[i].next){
        v = ex[i].num ;
        if( !dfn[v] ){
            tarjin(v) ;
            if( low[v] < low[u])    low[u] = low[v] ;
        }
        else if( in[v] && dfn[v] < low[u])
            low[u] = dfn[v] ;
    }
    if( low[u] == dfn[u] ){
        Bcnt++;
        do{
            v = stack[top--] ; in[v] = 0 ;
            col[v] = Bcnt ;
        }while(u!=v) ;

    }
}
void solve(){
    idx = Bcnt = top= 0 ;
    memset(dfn , 0, sizeof(dfn));
    memset(in, 0 ,sizeof(in));
    for(int i=1;i<=2*N;i++){
        if( !dfn[i] )   tarjin(i) ;
    }
    bool ok = 1 ;
    for(int i=1;i<=N;i++){
        if( col[2*i-1]==col[2*i] ){
            ok = 0 ;    break ;
        }
    }
    if( ok )    printf("YES\n");
    else        printf("NO\n");
}
int main(){
    int a, b ,c ,d;
    char ch[10] ;
    while(scanf("%d%d",&N,&M) == 2){
        init() ;
        for(int i=1;i<=M;i++){
            scanf("%d%d%d%s",&a,&b,&c,ch) ;
            a ++ ; b ++ ;
            if(ch[0]=='A')     d = 0 ;
            else if(ch[0]=='O') d = 1 ;
            else                d = 2 ;
            add(a,b,c,d);   add(b,a,c,d);
        }
        for(int u=1;u<=N;u++){
            for(int j=root[u] ;j!=-1;j=edge[j].next){
                int v = edge[j].num ;
                int val = edge[j].val ;
                int f = edge[j].flag ;

                if(val == 0){
                    if(f == 0){     //AND
                        add2(2*u,2*v-1);
                    }
                    else if(f == 1){    //OR
                        add2(2*u-1, 2*v-1);
                        add2(2*u,2*u-1);
                    }
                    else{           //XOR
                        add2(2*u,2*v);
                        add2(2*u-1,2*v-1);
                    }
                }
                else{
                    if(f == 0){
                        add2(2*u, 2*v);
                        add2(2*u-1,2*u);
                    }
                    else if(f == 1){
                        add2(2*u-1,2*v);
                    }
                    else{
                        add2(2*u,2*v-1);
                        add2(2*u-1,2*v);
                    }
                }
            }
        }
        solve() ;
    }
    return 0 ;
}