POJ 3678 Katu Puzzle 2-sat 判断是不是有合法解

2012-07-20

POJ 3678 Katu Puzzle2-sat判断是否有合法解建图如下AND1a0-a1,b0-b1AND0a1-b0,b1-a0OR1a0-b1,b0-a1

POJ 3678 Katu Puzzle 2-sat 判断是否有合法解

建图如下

AND 1 a0->a1,b0->b1
AND 0 a1->b0,b1->a0
OR 1 a0->b1,b0->a1
OR 0 a1->a0,b1->b0
XOR 1 a0->b1,a1->b0,b1->a0,b0->a1
XOR 0 a0->b0,b0->a0,a1->b1,b1->a1

需要注意的是，如果a,b的值已经确定，比如说and 1 操作的时候，a,b的值都只能是1，那么需要加 a0->a1,b0->b1，这种加边跟平常的加边情况不同，具体请看 http://blog.sina.com.cn/s/blog_68629c7701010gf1.html

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>#define MAXN 10005#define MAXM 4000005#define INF 1000000000using namespace std;struct Edge{    int v, next;}edge[MAXM];int n, m, e, head[MAXN];int scc, index, fa[MAXN];int instack[MAXN], low[MAXN], dfn[MAXN];int st[MAXN], top;void init(){    e = scc = index = top = 0;    memset(head, -1, sizeof(head));    memset(instack, 0, sizeof(instack));    memset(dfn, 0, sizeof(dfn));}void insert(int x, int y){    edge[e].v = y;    edge[e].next = head[x];    head[x] = e++;}void tarjan(int u){    int v;    dfn[u] = low[u] = ++index;    st[++top] = u;    instack[u] = 1;    for(int i = head[u]; i != -1; i = edge[i].next)    {        v = edge[i].v;        if(!dfn[v])        {            tarjan(v);            low[u] = min(low[u], low[v]);        }        else if(instack[v]) low[u] = min(low[u], dfn[v]);    }    if(dfn[u] == low[u])    {        scc++;        do        {            v = st[top--];            instack[v] = 0;            fa[v] = scc;        }while(v != u);    }}void build(){    char s[15];    int x, y, w;    while(m--)    {        scanf("%d%d%d%s", &x, &y, &w, s);        x++; y++;        if(s[0] == 'A')        {            if(w == 0)            {                insert(x + n, y);                insert(y + n, x);            }            else            {                insert(x, x + n);                insert(y, y + n);            }        }        else if(s[0] == 'O')        {            if(w == 0)            {                insert(x + n, x);                insert(y + n, y);            }            else            {                insert(x, y + n);                insert(y, x + n);            }        }        else        {            if(w == 0)            {                insert(x + n, y + n);                insert(x, y);                insert(y, x);                insert(y + n, x + n);            }            else            {                insert(x, y + n);                insert(y, x + n);                insert(y + n, x);                insert(x + n, y);            }        }    }}bool check(){    for(int i = 1; i <= n; i++)        if(fa[i] == fa[i + n]) return false;    return true;}void solve(){    for(int i = 1; i <= 2 * n; i++)        if(!dfn[i]) tarjan(i);    if(check()) printf("YES\n");    else printf("NO\n");}int main(){    while(scanf("%d%d", &n, &m) != EOF)    {        init();        build();        solve();    }    return 0;}

热点排行

编程

POJ 3678 Katu Puzzle 2-sat 判断是不是有合法解