暑假集训 || 2-SAT

推荐论文：https://blog.csdn.net/zixiaqian/article/details/4492926

2-SAT问题是2判定性问题，给出n个集合，每个集合中有两个元素，两个元素之一要出现，且有一些元素不能相互共存

考虑每个集合中的元素都为i 和 i'，对于每组信息在他们之间连边，连上边就绑定啦，它们一定要一起选

如果有一个点必须选又必须不选，就是矛盾

有N对物品，每对物品中必须选取一个，也只能选取一个，并且它们之间存在某些限制关系

2-sat中一条有向边的涵义是选了起点就必须选终点

模板：solve表示能否按规则取出，vis中标记为1的元素即为最终取出的元素

bool dfs(int u)

{

    if(vis[u]) return true;

    if(vis[u^]) return false;

    s[cnt++] = u;

    vis[u] = ;

    for(int i = head[u];i;i = nxt[i])

    {

        int v = l[i];

        if(!dfs(v))

            return false;

    }

    return true;

}

bool solve()

{

    for(int i = ; i < n; i++)

    {

        if(!vis[i<<] && !vis[i<<|])

        {

            cnt = ;

            if(!dfs(i<<))

            {

                while(cnt) vis[s[--cnt]] = false;

                if(!dfs(i<<|)) return false;

            }

        }

    }

    return true;

}

HDU 1814

题意：n个党派要参加会议，每个党派有两个人，要派出一个人去参加，有些人不能同时去，求输出字典序最小的方案

思路：裸题，要求字典序最小就从前面开始搜就可以了

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

const int maxn = ;

const int maxm = ;

const int INF = ;

int head[maxm], nxt[maxm], l[maxm], tot = ;

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

int n, m, cnt, vis[maxn], s[maxn];

void init()

{

    memset(head, , sizeof(head));

    tot = ;

    memset(vis, , sizeof(vis));

}

bool dfs(int u)

{

    if(vis[u]) return true;

    if(vis[u^]) return false;

    s[cnt++] = u;

    vis[u] = ;

    for(int i = head[u];i;i = nxt[i])

    {

        int v = l[i];

        if(!dfs(v))

            return false;

    }

    return true;

}

bool solve()

{

    for(int i = ; i < n; i++)

    {

        if(!vis[i<<] && !vis[i<<|])

        {

            cnt = ;

            if(!dfs(i<<))

            {

                while(cnt) vis[s[--cnt]] = false;

                if(!dfs(i<<|)) return false;

            }

        }

    }

    return true;

}

int main()

{

    while(~scanf("%d %d", &n, &m))

    {

        init();

        for(int i = ; i < m; i++)

        {

            int a, b;

            scanf("%d %d", &a, &b);

            build(a-, (b-)^);

            build(b-, (a-)^);

        }

        if(solve())

        {

            for(int i = ; i < n; i++)

            {

                if(vis[i<<]) printf("%d\n", i<<|);

                else printf("%d\n", (i<<)+);

            }

        }

        else printf("NIE\n");

    }

    return ;

}

POJ 3648

题意：有n-1对夫妇参加新娘新郎的婚礼，每对夫妇要坐对面，且有些对有（奸情）的不能同时坐在新娘的对面，问新娘这一侧都坐了谁

思路：看起来就是2-SAT问题，每一对夫妇是一个集合

因为新娘这一侧是可以有冲突的！！所以要考虑我们求新娘对面都坐了谁

这样的话我们就不能选新娘

连一条新娘向新郎的边，如果选了新娘，那么就要选新郎，就产生冲突了，判为不行

思路好神奇哇

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

const int maxn = ;

const int maxm = ;

const int INF = ;

int head[maxm], nxt[maxm], l[maxm], tot = ;

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

int n, m, cnt, vis[maxn], s[maxn];

void init()

{

    memset(head, , sizeof(head));

    tot = ;

    memset(vis, , sizeof(vis));

}

bool dfs(int u)

{

    if(vis[u]) return true;

    if(vis[u^]) return false;

    s[cnt++] = u;

    vis[u] = ;

    for(int i = head[u];i;i = nxt[i])

    {

        int v = l[i];

        if(!dfs(v))

            return false;

    }

    return true;

}

bool solve()

{

    for(int i = ; i < n; i++)

    {

        if(!vis[i<<] && !vis[i<<|])

        {

            cnt = ;

            if(!dfs(i<<))

            {

                while(cnt) vis[s[--cnt]] = false;

                if(!dfs(i<<|)) return false;

            }

        }

    }

    return true;

}

int cal(int x, char c)

{

    if(c == 'h') return x<<;

    if(c == 'w') return x<<|;

}

int main()

{

    while()

    {

        scanf("%d %d", &n, &m);

        if(n ==  && m == ) break;

        init();

        for(int i = ; i < m; i++)

        {

            int a, b;

            char c, d;

            scanf("%d%c%d%c", &a, &c, &b, &d);

            a = cal(a, c);

            b = cal(b, d);

            build(a, b^);

            build(b, a^);

        }

        build(, );

        if(solve())

        {

            for(int i = ; i < n; i++)

            {

                if(i > ) printf(" ");

                printf("%d", i);

                if(vis[i<<]) printf("w");

                else printf("h");

            }

            printf("\n");

        }

        else printf("bad luck\n");

    }

    return ;

}

题意：0 ~ n-1这n个数，给出两个数之间AND OR 或者 XOR的值，问能否推断出这几个数都是什么

思路：n个数对应n个集合，每个数为0或1对应一个集合中的i 和 i'，

a and b == 1, 这种情况a和b必须取1，所以连边a’->a, b’->b.
a and b == 0, 这种情况a和b不能同时为1，所以连边a->b’, b->a’.
a or b == 1, 这种情况a和b不能同时为0，所以连边a’->b, b’->a.
a or b == 0, 这种情况a和b必须同时为0，所以连边a->a’, b->b’.
a xor b == 1, 这种情况a和b取值要相反，所以连边a->b’, a’->b, b->a’, b’->a.
a xor b == 0, 这种情况a和b取值要相同，所以连边a->b, b->a, a’->b’, b’->a’.

也可以这么想：

x,y代表当前的式子未知数..x0为x选0的点..x1为x选1的点...y0,y1同样..

1、x AND y = 1 .. 表明x , y必须为1...所以不能选择x0,y0...这个东西要表示出来..就让选择x0,y0直接就自我矛盾..加边 ( x0,x1 ) , ( y0,y1 )

2、x AND y = 0 ..表明x,y至少有一个为0...那么加边 ( x1,y0 ) , ( y1,x0 )

3、x OR y = 1 ...表明x,y至少有一个味1..那么加边 ( x0,y1 ) , ( y0,x1 )

4、x OR y = 0..表明x,y都为0...所以让选择x1,y1就直接自矛盾 ( x1,x0 ) , ( y1,y0 )

5、x XOR y = 1..表明x,y不同..那么加边 ( x0,y1 ) , ( x1,y0 ) ,( y0,x1 ) , ( y1,x0 )

6、x XOR y = 0..表明x,y是相同的..那么加边 ( x0,y0 ) , ( x1,y1 ) ,( y0,x0 ) , ( y1,x1 )

tarjan看一个集合中的两个点是不是在同一个环里，在的话就凉凉

主要还是在于建图

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

const int SZ = ;

const int INF = ;

int head[SZ], nxt[SZ], l[SZ], tot = ;

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

int n, m;

stack<int> s;

int dfn[], low[], clock = ;

int sccnum[], cnt = ;

void dfs(int u)

{

    dfn[u] = low[u] = ++clock;

    s.push(u);

    for(int i = head[u]; i; i = nxt[i])

    {

        int v = l[i];

        if(!dfn[v])

        {

            dfs(v);

            low[u] = min(low[u], low[v]);

        }

        else if(!sccnum[v])

            low[u] = min(low[u], dfn[v]);

    }

    if(low[u] == dfn[u])

    {

        cnt++;

        while()

        {

            int v = s.top();

            s.pop();

            sccnum[v] = cnt;

            if(u == v) break;

        }

    }

}

void tarjan()

{

    for(int i = ; i < n<<; i++)

        if(!dfn[i]) dfs(i);

}

void init()

{

    memset(head, , sizeof(head));

    tot = ;

    memset(dfn, , sizeof(dfn));

    memset(low, , sizeof(low));

    clock = ;

    while(s.size()) s.pop();

    cnt = ;

    memset(sccnum, , sizeof(sccnum));

}

int main()

{

    while(~scanf("%d %d", &n, &m))

    {

        init();

        for(int i = ; i < m; i++)

        {

            int a, b, c;

            char op[];

            scanf("%d%d%d%s", &a, &b, &c, op);

            if(op[] == 'A')

            {

                if(c == ) build(a<<|, a<<), build(b<<|, b<<);

                if(c == ) build(a<<, b<<|), build(b<<, a<<|);

            }

            if(op[] == 'O')

            {

                if(c == ) build(a<<|, b<<), build(b<<|, a<<);

                if(c == ) build(a<<, a<<|), build(b<<, b<<|);

            }

            if(op[] == 'X')

            {

                if(c == ) build(a<<, b<<|), build(a<<|, b<<), build(b<<, a<<|), build(b<<|, a<<);

                if(c == ) build(a<<, b<<), build(b<<, a<<), build(a<<|, b<<|), build(b<<|, a<<|);

            }

        }

        tarjan();

        bool flag = true;

        for(int i = ; i < n; i++)

            if(sccnum[i<<] == sccnum[i<<|]) flag = false;

        if(flag) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

POJ 3207

题意：一个圈上顺着排0,1,...,n-1号点，给出m条边，每条边可以从圆内走也可以从圆外走，问这些边可不可以不相交

思路：对于每条Link，要么在圆外，要么在圆内，且不可同时满足，只能两者取一，判断这M条Link是否合法，也就是M条Link不冲突，这就是典型的2-sat问题了。

将每条Link i 看做一个点，如果Link在圆内，则选做i ，如果在圆外，则选做i'。对于两条线(i,j) ，如果i，j不能同时在圆内，也就可以推出两者不能同时在圆外

如果这两条边冲突，那么balabala连边

构图方式神奇↓

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <stack>

using namespace std;

const int maxn = ;

const int maxm = ;

const int INF = ;

int head[maxm], nxt[maxm], l[maxm], tot = ;

struct Edge

{

    int f, t;

}e[];

void build(int f, int t)

{

    l[++tot] = t;

    nxt[tot] = head[f];

    head[f] = tot;

}

int n, m, cnt, vis[maxn], s[maxn];

void init()

{

    memset(head, , sizeof(head));

    tot = ;

    memset(vis, , sizeof(vis));

}

bool dfs(int u)

{

    if(vis[u]) return true;

    if(vis[u^]) return false;

    s[cnt++] = u;

    vis[u] = ;

    for(int i = head[u]; i; i = nxt[i])

    {

        int v = l[i];

        if(!dfs(v))

            return false;

    }

    return true;

}

bool solve()

{

    for(int i = ; i < m; i++)

    {

        if(!vis[i<<] && !vis[i<<|])

        {

            cnt = ;

            if(!dfs(i<<))

            {

                while(cnt) vis[s[--cnt]] = false;

                if(!dfs(i<<|)) return false;

            }

        }

    }

    return true;

}

int main()

{

    scanf("%d %d", &n, &m);

    for(int i = ; i < m; i++)

    {

        int a, b;

        scanf("%d%d", &a, &b);

        e[i].f = min(a, b);

        e[i].t = max(a, b);

    }

    for(int i = ; i < m; i++)

        for(int j = i+; j < m; j++)

            if((e[j].f<e[i].f && e[j].t<e[i].t && e[j].t>e[i].f) || (e[j].f>e[i].f && e[j].f<e[i].t && e[j].t>e[i].t))

            {

                build(i<<, j<<|);

                build(j<<, i<<|);

                build(i<<|, j<<);

                build(j<<|, i<<);

            }

    if(solve()) printf("panda is telling the truth...\n");

    else printf("the evil panda is lying again\n");

    return ;

}

巴特西

暑假集训 || 2-SAT

最新文章

热门文章