Menu
Article 2-SAT

2-SAT专题(1)

NodeKey

NodeKey

• 11 min read

附带我的学习来源，这里包含以上所有题目的题解和代码。实在想不出来我就是看这里的。

1. HDU 3062 Party

题意：
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？ （中文题面就复制粘贴一下了……）

思路：
非常典型的 2-sat 模型，如果两对夫妻 A B ，丈夫A0 与 妻子B1 有仇，那么就建 A0 -> B0 , A1 -> B1 两条边。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2005;

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

struct node {
    int to;
    int nxt;
} edges[1005 * 1005 * 2];

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

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

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]) {
            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 (v != u);
    }
}

int main()
{
    int a1, a2, c1, c2;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d",&a1,&a2,&c1,&c2);
            addEdge((a1 << 1) + c1, (a2 << 1 | 1) - c2);
            addEdge((a2 << 1) + c2, (a1 << 1 | 1) - c1);
        }
        for (int i = 0; i < 2 * n; i++)
            if (dfn[i] == 0)
                tarjan(i);
        bool flag = true;
        for (int i = 0; i < n; i++)
            if (color[i << 1] == color[i << 1 | 1]) {
                flag = false;
                break;
            }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

2. HDU 1824 Let’s go home

题意：
入门2-sat，稍微有点的变化就是两方中有一方是集合。

思路：
其实这并没有什么关系，就算是两个集合，A，B（ 第i对 ），那么把 A 的所有集合赋值为 i<<1，B 则为 i<<1|1 。再根据他的要求，由编号索引到集合号，建边即可。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 1010, kmax = 5050;

int n, m, idx, scc, top, vis_time;
int kpair[kmax];
int head[maxn << 1];
int dfn[kmax], low[kmax], st[kmax], color[kmax];
bool instack[kmax];

struct node {
    int to;
    int nxt;
} edges[kmax];

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

void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, -1, sizeof dfn);
    memset(instack, false, sizeof instack);
    vis_time = top = idx = scc = 0;
}

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 (v != u);
    }
}

int main()
{
    int a, b, c, ka, kb;
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &a, &b, &c);
            kpair[a] = i << 1;
            kpair[b] = i << 1 | 1;
            kpair[c] = i << 1 | 1;
        }
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &a, &b);
            ka = kpair[a];
            kb = kpair[b];
            addEdge(ka, kb ^ 1);
            addEdge(kb, ka ^ 1);
        }
        for (int i = 0; i < 2 * n; i++)
            if (dfn[i] == -1)
                tarjan(i);
        bool flag = true;
        for (int i = 0; i < n; i++)
            if (color[i << 1] == color[i << 1 | 1]) {
                flag = false;
                break;
            }
        puts(flag ? "yes" : "no");
    }
    return 0;
}

3. POJ 3207 Ikki’s Story IV – Panda’s Trick

题意：
一个圆上有 n 个点，现在有 m 条边分别连接这 n 个点。连接方式分在圆内和圆外。问是否存在这样一种方案能满足这 m 条边。

思路：
对于这 m 条边我们两两进行判断。如果存在相交情况，那么这两条线将不能在同一侧，相交效果见下图。

相交

这在一维的表现是两条线段，相交但不包含。不包含！！！不包含！！！！

值得一提的是，对于两条线段，如果在圆内是相交的，那么在圆外也必然相交。所以一次判断相交要建立四条边。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 2010, kmax = 5050;

int n, m, idx, scc, top, vis_time;
int kpair[kmax];
int head[maxn << 1], le[maxn], ri[maxn];
int dfn[kmax], low[kmax], st[kmax], color[kmax];
bool instack[kmax];

struct node {
    int to;
    int nxt;
} edges[505 * 505 * 4];

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

void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, -1, sizeof dfn);
    memset(instack, false, sizeof instack);
    vis_time = top = idx = scc = 0;
}

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 (v != u);
    }
}

inline bool judge(int a, int b)
{
    if (le[a] > le[b])
        swap(a, b);
    return ri[a] > le[b] && ri[b] > ri[a];
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d", le + i, ri + i);
            if (le[i] > ri[i])
                swap(le[i], ri[i]);
        }
        for (int i = 0; i < m; i++)
            for (int j = i + 1; j < m; j++)
                if (judge(i, j)) {
                    addEdge(i << 1, j << 1 | 1);
                    addEdge(i << 1 | 1, j << 1);
                    addEdge(j << 1, i << 1 | 1);
                    addEdge(j << 1 | 1, i << 1);
                }
        for (int i = 0; i < m * 2; i++)
            if (dfn[i] == -1)
                tarjan(i);
        bool flag = true;
        for (int i = 0; i < m; i++)
            if (color[i << 1] == color[i << 1 | 1]) {
                flag = false;
                break;
            }
        puts(flag ? "panda is telling the truth..." : "the evil panda is lying again");
    }
    return 0;
}

4. POJ 3678 Katu Puzzle

题意：
有n个未知数，取值只能为 0或1，给你 m 个限制。

$$X_i op X_j = c$$

问你是否存在这样 n 个数使得所有限制都成立。

思路：
2-sat建图题，把每个值是1(a)和0(~a)为两种状态。
AND 结果为1：建边 x->x,y->y （两个数必须全为1)
（对于这里我不是很理解，一开始我写的是 x -> y , y -> x 。

AND 结果为0：建边 y->x,x->y （两个数至少有一个为0）
OR 结果为1：建边 x->y,y->x （两个数至少有一个为1）
OR 结果为0：建边 x->x,y->y （两个数必须全为0）
XOR 结果为1：建边 x->y,y->x,y->x,x->y （两个数必须不同）
XOR 结果为0：建边 x->y,y->x,x->y,y->x （两个数必须相同）

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 1010 * 2, kmax = 1e6 + 5;

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

struct node {
    int to;
    int nxt;
} edges[kmax << 1];

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

void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, -1, sizeof dfn);
    memset(instack, false, sizeof instack);
    vis_time = top = idx = scc = 0;
}

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 (v != u);
    }
}

int main()
{
    int a, b, res;
    char op[5];
    while (scanf("%d %d", &n, &m) != EOF) {
        init();
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %s", &a, &b, &res, op);
            if (op[0] == 'A') {
                if (res) {
                    addEdge(a << 1, a << 1 | 1);
                    addEdge(b << 1, b << 1 | 1);
                } else {
                    addEdge(a << 1 | 1, b << 1);
                    addEdge(b << 1 | 1, a << 1);
                }
            } else if (op[0] == 'O') {
                if (res) {
                    addEdge(a << 1, b << 1 | 1);
                    addEdge(b << 1, a << 1 | 1);
                } else {
                    addEdge(a << 1 | 1, a << 1);
                    addEdge(b << 1 | 1, b << 1);
                }
            } else {
                if (res) {
                    addEdge(a << 1, b << 1 | 1);
                    addEdge(b << 1, a << 1 | 1);
                    addEdge(a << 1 | 1, b << 1);
                    addEdge(b << 1 | 1, a << 1);
                } else {
                    addEdge(a << 1, b << 1);
                    addEdge(b << 1, a << 1);
                    addEdge(a << 1 | 1, b << 1 | 1);
                    addEdge(b << 1 | 1, a << 1 | 1);
                }
            }
        }
        for (int i = 0; i < 2 * n; i++)
            if (dfn[i] == -1)
                tarjan(i);
        bool flag = true;
        for (int i = 0; i < n; i++)
            if (color[i << 1] == color[i << 1 | 1]) {
                flag = false;
                break;
            }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

5.HDU 3622 Bomb Game

题意:
有n组炸弹，一组两个，位置固定，你必须从中选出任意一个，使得所有炸弹单独爆炸都不会波及到其他任意炸弹，炸弹范围自定，求最大的炸弹爆炸范围。

思路:
对范围进行二分，对每一个 mid 进行 2-sat 判定即可。

如何建图？
昨天好好反思了一下这个问题，2-sat就是解决二重适应性问题，如果存在一个矛盾，那么就必须对它进行处理，否则，无需处理。例如，如果第 i 组第一个炸弹与第 j 组第一个炸弹范围重叠，那么 i 组 1 号炸弹必须得与 j 组 2 号炸弹相连，在这个条件下，这是必须满足的。因为爆炸是双向的，所以第 j 组 1 号炸弹必须与第 i 组 2 号炸弹相连。

因为爆炸是双向的，所以我们只需要建立 i = (0..n) j = (i+1..n) 的循环即可，否则会代码写丑很容易超时。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int maxn = 205;
const double eps = 1e-6;

int n;
double dis[maxn][2][maxn][2];
int head[maxn];
int instack[maxn], dfn[maxn], low[maxn], st[maxn], color[maxn];
int vis_time, top, idx, scc;

struct double_node {
    int x[2], y[2];
} nodes[maxn];

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

inline double func(int i, int a, int j, int b)
{
    return (double)(nodes[i].x[a] - nodes[j].x[b]) * (nodes[i].x[a] - nodes[j].x[b]) + (nodes[i].y[a] - nodes[j].y[b]) * (nodes[i].y[a] - nodes[j].y[b]);
}

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

void init()
{
    memset(head, -1, sizeof head);
    memset(dfn, -1, sizeof dfn);
    memset(instack, false, sizeof instack);
    vis_time = top = idx = scc = 0;
}

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 (v != u);
    }
}

bool judge(double radius)
{
    init();
    radius = 4 * radius * radius;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            if (dis[i][0][j][0] < radius) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (dis[i][0][j][1] < radius) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (dis[i][1][j][0] < radius) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
            if (dis[i][1][j][1] < radius) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
        }
    for (int i = 0; i < 2 * n; i++)
        if (dfn[i] == -1)
            tarjan(i);
    bool flag = true;
    for (int i = 0; i < n; i++)
        if (color[i << 1] == color[i << 1 | 1]) {
            flag = false;
            break;
        }
    return flag ? true : false;
}

int main()
{
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%d %d %d %d", &nodes[i].x[0], &nodes[i].y[0], &nodes[i].x[1], &nodes[i].y[1]);
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++) {
                dis[i][0][j][0] = func(i, 0, j, 0);
                dis[i][0][j][1] = func(i, 0, j, 1);
                dis[i][1][j][0] = func(i, 1, j, 0);
                dis[i][1][j][1] = func(i, 1, j, 1);
            }
        double l = 0, r = 14500, mid, ans=10000;
        while (l + eps < r) {
            mid = (l + r) / 2;
            if (judge(mid)) {
                ans = mid;
                l = mid + eps;
            } else
                r = mid - eps;
        }
        printf("%.2f\n", ans);
    }
    return 0;
}
Share