Menu
Article 2-SAT

2-SAT专题(3)

NodeKey

NodeKey

• 6 min read

11.HDU 1814 Peaceful Commission

题意：
建图老题意，表示有n对人要出席一个会议，但是有m个恶劣的关系不允许同时出现。
但是不一样的地方就是需要输出可行解的最小序列

思路：
让你判断一下还是很简单的，但是输出最小序列真的让博主感到很无力，想了很长时间也没有一个快速的方法。看了题解是说暴搜索可解，我这里說一下暴搜思路。

先将所有节点染成白色（初始化），再进行遍历。如果已经染成红色或者黑色的节点就跳过，否则，我们先尝试将第一个节点染成红色，再进行暴力dfs缩点，暴力过程中，优先让第一个节点染成红色，第二个染成黑色。如果没有任何冲突，则表示缩点成功。否则尝试将第二个节点染成红色，再缩点，如果还不行，就说明无解了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define R 1
#define B 2
#define W 0

using namespace std;

const int maxn = 16005;
int n, m, idx, cnt;
int head[maxn], color[maxn], tmp[maxn];

struct node {
    int to;
    int nxt;
} edges[maxn << 4];

void init()
{
    n <<= 1;
    for (int i = 0; i <= n; i++)
        head[i] = -1;
}

void addEdge(const int& u, const int& v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

bool dfs(int u)
{
    if (color[u] == R)
        return true;
    if (color[u] == B)
        return false;
    color[u] = R, color[u ^ 1] = B;
    tmp[cnt++] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt) {
        if (!dfs(edges[id].to))
            return false;
    }
    return true;
}

bool solve()
{
    memset(color, 0, sizeof color);
    for (int i = 0; i < n; i += 2) {
        if (color[i])
            continue;
        cnt = 0;
        if (!dfs(i)) {
            for (int j = 0; j < cnt; j++)
                color[tmp[j]] = color[tmp[j] ^ 1] = W;
            if (!dfs(i ^ 1))
                return false;
        }
    }
    return true;
}

int main()
{
    int u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        while (m--) {
            scanf("%d %d", &u, &v);
            u--, v--;
            addEdge(u, v ^ 1);
            addEdge(v, u ^ 1);
        }
        if (solve()) {
            for (int i = 0; i < n; i++)
                if (color[i] == R)
                    printf("%d\n", i + 1);
        } else
            puts("NIE");
    }
    return 0;
}

12. POJ 3683 Priest John’s Busiest Day

13. POJ 3648 Wedding

14. POJ 3905 Perfect Election

15. HDU 4115 Eliminate the Conflict

题意：
n轮猜拳，已知对方所有出的结果，但是会给你一些限制，比如某两次你出的必须相同，或者必须不同。如果有某一局你输了或者破坏了规则，那么你就输了。

思路：
因为是猜拳，作为一个初学者，我以自身来说很容易陷入3-sat的误区，实则不然。真正决定n-sat的关键因素是 限制句子中的变量数目 ，比如这里第 u 次和第 v 次必须相同或者不同，只有两个变量就必然可以用2-sat做。

这里的限制，除了相同与不同外，对于一个已知的对方猜拳结果，那么我只有两个选择才能保证不输。
比如已知对方会出剪刀(S)，那么我要么出石头(R)，要么出剪刀(S)。
因此建边 ~S -> R , ~R -> S 。

额外的，从最开始就有的，如果我这局出了剪刀(S) ， 那么很自然地就不会是石头(R)或者布(P)了，可以换种说法，同时出 剪刀和石头 或者 剪刀和布 是矛盾的。

建边 S -> ~R , S-> ~P

我这个思路总共要建三次边……，可能有些麻烦了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <vector>

using namespace std;

const int maxn = 60010;
int n, m, idx, scc, vis_time, top;
int head[maxn], color[maxn], st[maxn], dfn[maxn], low[maxn];
bool instack[maxn];

struct node {
    int to;
    int nxt;
} edges[maxn * 20];

void init()
{
    for (int i = 0; i <= n * 6; i++) {
        dfn[i] = head[i] = -1;
        instack[i] = false;
    }
    idx = scc = vis_time = top = 0;
}

void addEdge(const int& u, const int& v)
{
    edges[idx].to = v;
    edges[idx].nxt = head[u];
    head[u] = idx++;
}

void tarjan(int u)
{
    int v;
    low[u] = dfn[u] = vis_time++;
    instack[u] = true;
    st[++top] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt) {
        v = edges[id].to;
        if (dfn[v] == -1) {
            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] = false;
            color[v] = scc;
        } while (u != v);
    }
}

int main()
{
    int T, u, v, k, r;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d %d", &n, &m);
        init();
        int six, win;
        for (int i = 0; i < n; i++) {
            six = i * 6;
            addEdge(six + 0, six + 3);
            addEdge(six + 0, six + 5);
            addEdge(six + 2, six + 1);
            addEdge(six + 2, six + 5);
            addEdge(six + 4, six + 1);
            addEdge(six + 4, six + 3);
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &r);
            r--;
            six = 6 * i;
            win = (r + 1) % 3;
            win <<= 1, r <<= 1;
            addEdge(six + (r ^ 1), six + win);
            addEdge(six + (win ^ 1), six + r);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &u, &v, &k);
            u--, v--;
            int sixu = u * 6, sixv = 6 * v;
            if (k) {
                addEdge(sixu + 0, sixv + 1);
                addEdge(sixu + 2, sixv + 3);
                addEdge(sixu + 4, sixv + 5);

                addEdge(sixv + 0, sixu + 1);
                addEdge(sixv + 2, sixu + 3);
                addEdge(sixv + 4, sixu + 5);
            } else {
                addEdge(sixu + 0, sixv + 0);
                addEdge(sixu + 2, sixv + 2);
                addEdge(sixu + 4, sixv + 4);

                addEdge(sixv + 0, sixu + 0);
                addEdge(sixv + 2, sixu + 2);
                addEdge(sixv + 4, sixu + 4);
            }
        }
        for (int i = 0; i < 6 * n; i++)
            if (dfn[i] == -1)
                tarjan(i);
        bool flag = true;
        for (int i = 0; i < 3 * n; i++)
            if (color[i << 1] == color[i << 1 | 1]) {
                flag = false;
                break;
            }
        printf("Case #%d: ", cas);
        puts(flag ? "yes" : "no");
    }
    return 0;
}

16. 总结

至此，2-SAT专题基本结束了 (2017.6.2 POJ 挂了好久了……

不得不说，2-SAT的题目在这个强联通tarjan这个算法上考得很少，更多的是把重点放在逻辑性非常强的建边上，我这个菜鸡，很多题目都只能看题解感慨……修炼还是远远不够……

我这里小小总结一下我对2-SAT题目的着重点和做法。

  1. 找出限制语句 这是很关键的，一般的题目都会很明显地告诉你。
  2. 从限制中抓出一个一个矛盾。n-SAT是解决矛盾给出适应解的问题，在你的逻辑内，必须抓出每个矛盾并解决它才能保证你逻辑的严密性。
  3. 当然对于tarjan的理解也算比较重要，但只要以上两个处理的好，逻辑缜密，tarjan大都只是套模板而已。
Share