2-SAT 学习笔记

发表于 | 分类于 | | + s

模板及讲解

加边a->b 代表选了a的话b也得选
例如 x->x` 表示选了x就必须选x` ，所以这个值必为x

有a, not a, a or b, a and b, a xor b四种基本运算，例如：
1、A, B至少选一个：A'->B, B'->A (a or b)
2、A, B必须同时选：A->B, B->A (a and b)
3、A, B只能选一个：A->B', B->A' (a xor b)
4、A必选：A'->A (a)
5、A不能选：A->A' (not a)
6、A选或者B不选：A'->B', B->A' (a or not b)

2-SAT模板题：BZOJ 2199

#include<cstdio>    
#include<algorithm>    
#include<cstring>     
#include<vector>   
#define ms(i,j) memset(i,j, sizeof i);    
using namespace std; 
const int MAXN = 1000 + 5;
const char orz[10] = {'Y', 'N', '?'};
int n,m; 
int ans[MAXN];
struct twoSAT//这里标号从0开始 
{
    vector<int> G[MAXN*2];//邻接表 
    bool mark[MAXN*2];//每个点是否被标记 
    int n; 
    int init(int ni)//初始化 
    {
        n = ni;
        for (int i=0;i<2*n;i++) G[i].clear();
    }
    int addEdge(int x, int y, int xv, int yv)//加一个条件 
    {
        x = x*2+xv;
        y = y*2+yv;
        G[x^1].push_back(y);
        G[y^1].push_back(x);//2i是假，2i+1是真 
    }
    int dfs(int x)
    {
        if (mark[x^1]) return false;//对应点被标记，不符合要求 
        if (mark[x]) return true;//已经被标记直接返回
        mark[x] = true;//标记 
        for (int i=0;i<G[x].size();i++)//继续标记 
        {
            if (!dfs(G[x][i])) return false;
        } 
        return true;
    }
    int check(int x)//检查一个议案是否通过 
    {
        ms(mark, false); 
        return dfs(x);
    }
}ts;
int main()    
{     
    scanf("%d%d", &n,&m);
    ts.init(n);
    for (int i=0;i<m;i++)
    {
        int bi,ci;
        char vbi,vci;
        scanf("%d %c %d %c", &bi,&vbi,&ci,&vci);
        int vvbi = false, vvci = false;
        if (vbi=='Y') vvbi = true;
        if (vci=='Y') vvci = true;
        ts.addEdge(bi-1,ci-1,vvbi,vvci);
    }
    for (int i=0;i<n;i++)
    {
        int p = ts.check(i*2);
        int q = ts.check(i*2+1);
        if (!p&&!q) {printf("IMPOSSIBLE"); return 0;}
        if (p&&q) ans[i] = 2;
        else if (!p) ans[i] = 0;
        else ans[i] = 1;
    }
    for (int i=0;i<n;i++) putchar(orz[ans[i]]);
    return 0;    
}

Tarjan版本(Bzoj 1823)：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
int tb, n, m, belongs[2 * 100 + 5], vis[2 * 100 + 5], scc_num, dfn[2 * 100 + 5], low[2 * 100 + 5];
vector<int> G[2 * 100 + 5];//2x->m 2x+1->h
stack<int> s;
void tarjan(int u) {
    dfn[u] = low[u] = ++tb, vis[u] = -1, s.push(u);
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (vis[v] == 0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vis[v] == -1) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int e;
        scc_num++;
        do {
            e = s.top(); s.pop();
            belongs[e] = scc_num;
            vis[e] = 1;
        } while (e != u);
    }
}
int getss()
{
    char ans;
    while (true) {
        ans = getchar();
        if (ans == 'm') return 0;
        if (ans == 'h') return 1;
        int ret = 0;
        while (ans >= '0' && ans <= '9')  {
            ret = ret * 10 + ans - '0';
            ans = getchar();
        }
        if (ret > 0) return ret;
    }
}
void clean() {
    tb = scc_num = 0;
    for (int i = 0; i <= 2 * 100 + 1; i++) dfn[i] = low[i] = belongs[i] = vis[i] = 0, G[i].clear();
}
void solve() {
    scanf("%d%d", &n, &m);
    clean();
    char c1, c2;
    int a1, a2;
    for (int i = 1; i <= m; i++) {
        c1 = getss(), a1 = getss(), c2 = getss(), a2 = getss();
        int x = 2 * (a1 - 1) + (c1 == 1) , y = 2 * (a2 - 1) + (c2 == 1);
        G[x].push_back(y ^ 1), G[y].push_back(x ^ 1);
    }
    for (int i = 1; i <= n * 2; i++) if (!vis[i]) tarjan(i);
    for (int i = 1; i <= 2 * n; i += 2) {
        if (belongs[i] == belongs[i ^ 1]) {
            printf("BAD\n");
            return ;
        }
    }
    printf("GOOD\n");
} 
int main() {
    int T; scanf("%d", &T);
    while (T--) solve();
    return 0;
}
------ 本文结束 ------