ZOJ 3656 Bit Magic | The 2012 ACM-ICPC Asia Changchun Regional Contest – B

题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3656

针对数组A中所有数的的32位分别作satisfaction判定，每位有0-1两种取法，可以看出是2-sat模型；

建图参考：

a  AND  b = 1    <==>    _a->a  _b->b
a  AND  b = 0    <==>    a->_b  b->_a
a  OR   b = 1    <==>    _a->b  _b->a
a  OR   b = 0    <==>    a->_a  b->_b
a  XOR  b = 1    <==>    _a->b  a->_b  _b->a  b->_a
a  XOR  b = 0    <==>    a->b  _a->_b  b->a  _b->_a

六种情况都给用了……

贴代码；SyntaxHighlighter版本略低啊~~~~~~~~

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>

using namespace std;

#define MAXN 1010
int b[MAXN][MAXN], g[MAXN][MAXN];
int type[MAXN], stk[MAXN], dfn[MAXN], low[MAXN], depth, top, id;
bool instk[MAXN];
int n;
void build_map(int k)
{
    memset(g, 0, sizeof(g));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (i == j)     continue;
            else if (i % 2 == 1 && j % 2 == 1) {
                if (b[i][j] & (1 << k)) {
                    g[i][j+n] = 1;
                    g[j][i+n] = 1;
                }
                else {
                    g[i+n][i] = 1;
                    g[j+n][j] = 1;
                }
            }
            else if (i % 2 == 0 && j % 2 == 0) {
                if (b[i][j] & (1 << k)) {
                    g[i][i+n] = 1;
                    g[j][j+n] = 1;
                }
                else {
                    g[j+n][i] = 1;
                    g[i+n][j] = 1;
                }
            }
            else {
                if (b[i][j] & (1 << k)) {
                    g[i][j+n] = g[j+n][i] = 1;
                    g[j][i+n] = g[i+n][j] = 1;
                }
                else {
                    g[i][j] = g[j][i] = 1;
                    g[i+n][j+n] = g[j+n][i+n] = 1;
                }
            }
        }
}
void tarjan(int i)
{
    dfn[i] = low[i] = ++depth;
    stk[++top] = i;
    instk[i] = 1;
    for (int j = 0; j < n*2; j++) {
        if (g[i][j]) {
            if (!dfn[j]) {
                tarjan(j);
                low[i] = min(low[i], low[j]);
            }
            else {
                if (instk[j])
                    low[i] = min(low[i], dfn[j]);
            }
        }
    }
    int j;
    if (dfn[i] == low[i]) {
        id++;
        do {
            j = stk[top--];
            type[j] = id;
            instk[j] = 0;
        } while (i != j);
    }
}
void solve()
{
    for (int i = 0; i < 32; i++)
    {
        build_map(i);
        memset(type, 0, sizeof(type));
        memset(stk, 0, sizeof(stk));
        memset(dfn, 0, sizeof(dfn));
        memset(low, 0, sizeof(low));
        memset(instk, 0, sizeof(instk));
        depth = top = id = 0;
        for (int j = 0; j < n*2; j++)
            if (!dfn[j])
                tarjan(j);

        for (int i = 0; i < n; i++)
            if (type[i] == type[i+n])
            {
                printf("NOn");
                return;
            }
    }
    printf("YESn");
}
int main()
{
    while (scanf("%d", &n) == 1) {
        memset(type, 0, sizeof(type));
        memset(b, 0, sizeof(b));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &b[i][j]);
        bool flag = 0;
        for (int i = 0; i < n; i++)
            if (b[i][i]) {
                flag = 1;
                break;
            }
        if (flag) {
            printf("NOn");
            continue;
        }
        solve();
    }
    return 0;
}

• Regional Asia