Menu
Article 2-SAT

2-SAT专题(2)

NodeKey

NodeKey

• 11 min read

6. POJ 2296 Map Labeler

题意：
平面区域内部有n个点，以这个点为上底边中心或者下底边中心作正方形，要求使所有正方形都不相交，问正方形最大的边长为多少。

思路：
和炸弹那道题差不多，二分区间，判断即可。

令( Dis_x [a][b] = \left| x[a] – x[b] \right| , Dis_y [a][b] = \left| y[a] – y[b] \right| )，边长为 mid，设 a 表示 a 矩阵放上面，~a 表示 a 矩阵放下面。
建图：

  • (Dis_x[a][b] \geq mid ) 或者 ( Dis_y[a][b] \geq 2 \times mid ) 不处理
  • 否则 ( Dis_y[a][b] \geq mid ) 加边 ~a -> ~b , b -> a 。
  • 否则 (Dis_y[a][b] > 0 ) 加边 ~a -> a , b -> ~b 。 （其实就是表示，如果你选了 ~a , b 就会适应失败。
  • 否则 即 (Dis_y[a][b] = 0 ) 加边 a -> ~b , ~a -> b ,b -> ~a ,~b -> a 。

这里扯一句其他的，如果要求适应点为 n 数组一定要开 2n 呀！！！！

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

using namespace std;
const int maxn = 205;

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

struct point {
    int x, y;
    bool operator<(const point& a) const
    {
        return y > a.y;
    }
} points[maxn];

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

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;
        dfn[i] = -1;
        instack[i] = false;
    }
    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(int side)
{
    init();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (dis_x[i][j] < side && dis_y[i][j] < 2 * side) {
                if (dis_y[i][j] >= side) {
                    addEdge(i << 1 | 1, j << 1 | 1);
                    addEdge(j << 1, i << 1);
                } else if (dis_y[i][j] > 0) {
                    addEdge(i << 1 | 1, i << 1);
                    addEdge(j << 1, j << 1 | 1);
                } else {
                    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 < (n << 1); 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;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d %d", &points[i].x, &points[i].y);
        sort(points, points + n);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                dis_x[i][j] = abs(points[i].x - points[j].x);
                dis_y[i][j] = abs(points[i].y - points[j].y);
            }
        int le = 0, ri = 14500, mid;
        while (le <= ri) {
            mid = (le + ri) >> 1;
            if (judge(mid))
                le = mid + 1;
            else
                ri = mid - 1;
        }
        printf("%d\n", le - 1);
    }
    return 0;
}

7. HDU 3715 Go Deeper

题意：
给你一个递归函数，其参数分别为 深度dep 和三个其他的a,b,c。其中a,b都是另一个数组的ary的下标，如果ary[a]+ary[b]!=c 则可以向下递归。

思路：
因为所给的数据中，ary数组较小，最大深度较大，所以我们对深度进行二分。对每一个mid重新插入数据并跑一次2-sat即可。

写这道题的时候因为我的二分只是欠缺，导致一直A不了，补了一下二分后还好说。我的二分进阶

还请注意数组大小，开小了居然 G++是TLE ，C++是 WA

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

using namespace std;
const int maxn = 405;

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

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

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

void init(int k)
{
    for (int i = 0; i <= 2 * k; i++) {
        head[i] = -1;
        dfn[i] = -1;
        instack[i] = false;
    }
    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 void insertEdge(const int& a, const int& b, const int& c)
{
    if (c == 0) {
        addEdge(a << 1, b << 1 | 1);
        addEdge(b << 1, a << 1 | 1);
    } else if (c == 1) {
        addEdge(a << 1, b << 1);
        addEdge(b << 1, a << 1);
        addEdge(a << 1 | 1, b << 1 | 1);
        addEdge(b << 1 | 1, a << 1 | 1);
    } else {
        addEdge(a << 1 | 1, b << 1);
        addEdge(b << 1 | 1, a << 1);
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= m; i++)
            scanf("%d %d %d", a + i, b + i, c + i);
        int l = 0, r = m, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            init(n);
            for (int i = 1; i <= mid; i++)
                insertEdge(a[i], b[i], c[i]);
            bool flag = true;
            for (int i = 0; i < 2 * n; i++)
                if (dfn[i] == -1)
                    tarjan(i);
            for (int i = 0; i < n; i++)
                if (color[i << 1] == color[i << 1 | 1]) {
                    flag = false;
                    break;
                }
            if (flag)
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", l - 1);
    }
    return 0;
}

8. POJ 2749 Building roads

题意：
题目非常长……并且很繁琐，大意就是 n 个点要通过 一块中转站 进行相互连接。 中转站有两个提供选择，有些兄弟节点必须选择同一个中转站，有些仇人节点必须选择不同的中转站，每个节点和中转站的位置固定，要你使得任意节点之间的距离中的最大值最小。

思路：
傻了吧。
首先这种最值问题联系到二分肯定是没错了的。我们要求的这个距离 len 是在所有节点中是最大的，那么如果有两个节点的距离比我们的 len 要大，那么就产生了一个冲突。
因此我们只要二分这个 len 就可以了。

a 表示 a 节点选择 0 中转站 ，~a 表示 a 节点选择 1 中转站
dis[x][0] 表示 x 到 0 号中转站的距离，dis[x][1] 表示 x 到 1 号中转站的距离
d 表示 两个中转站的距离

建图：

情况1234
兄弟节点a -> b~a -> ~bb -> a~b -> ~a
仇人节点a -> ~b~a -> bb -> ~a~b -> a
dis[a][0]+dis[b][0] > lena -> ~bb -> ~a
dis[a][1]+dis[b][1] > len~a -> b~b -> a
dis[a][0]+dis[b][1] + d > lena -> b~b -> ~a
dis[a][1]+dis[b][0] + d > lena -> ~bb -> a
这里有一个 *小技巧*，是我无意之中发现的 可能有些人不知道，邻接表有一个性质：

通过备份 head 数组和 idx 可以还原回到任意位置。

就比如说我们这道题，兄弟节点与仇人节点最多会达到 8000 个操作，而我还原 heed 数组只要 1000 个操作，并省下一部分内存。至于这个性质为什么成立，熟悉邻接表的yy一下就可以得出来这是显然的。这里就不证明了。

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

using namespace std;
const int maxn = 2005;

int idx, n, scc, top, vis_time, a, b;
int head[maxn], dfn[maxn], low[maxn], color[maxn], st[maxn];
bool instack[maxn];
int tmp_head[maxn], tmp_idx;
int dis[maxn][2], s_dis;

int tx[maxn], ty[maxn];

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

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;
        dfn[i] = -1;
        instack[i] = false;
    }
    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(int mid)
{
    for (int i = 0; i <= 2 * n; i++) {
        dfn[i] = -1;
        instack[i] = false;
    }
    vis_time = top = scc = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (dis[i][0] + dis[j][0] > mid) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (dis[i][1] + dis[j][1] > mid) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (dis[i][0] + dis[j][1] + s_dis > mid) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (dis[i][1] + dis[j][0] + s_dis > mid) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
    for (int i = 0; i < (n << 1); i++)
        if (dfn[i] == -1)
            tarjan(i);
    for (int i = 0; i < n; i++)
        if (color[i << 1] == color[i << 1 | 1])
            return false;
    return true;
}

int main()
{
    int a, b, na, nb;
    int sx[2], sy[2];
    while (scanf("%d %d %d", &n, &a, &b) != EOF) {
        init();
        scanf("%d %d %d %d", &sx[0], &sy[0], &sx[1], &sy[1]);
        s_dis = abs(sx[0] - sx[1]) + abs(sy[0] - sy[1]);
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &na, &nb);
            dis[i][0] = abs(na - sx[0]) + abs(nb - sy[0]);
            dis[i][1] = abs(na - sx[1]) + abs(nb - sy[1]);
        }
        for (int i = 0; i < a; i++) {
            scanf("%d %d", &na, &nb);
            na--, nb--;
            addEdge(na << 1, nb << 1 | 1);
            addEdge(na << 1 | 1, nb << 1);
            addEdge(nb << 1, na << 1 | 1);
            addEdge(nb << 1 | 1, na << 1);
        }
        for (int i = 0; i < b; i++) {
            scanf("%d %d", &na, &nb);
            na--, nb--;
            addEdge(na << 1, nb << 1);
            addEdge(na << 1 | 1, nb << 1 | 1);
            addEdge(nb << 1, na << 1);
            addEdge(nb << 1 | 1, na << 1 | 1);
        }
        memcpy(tmp_head, head, sizeof head);
        tmp_idx = idx;

        int le = 0, ri = 4000000, mid;
        while (le <= ri) {
            mid = (le + ri) >> 1;
            if (judge(mid))
                ri = mid - 1;
            else
                le = mid + 1;
            memcpy(head, tmp_head, sizeof tmp_head);
            idx = tmp_idx;
        }
        printf("%d\n", ri == 4000000 ? -1 : ri + 1);
    }
    return 0;
}

9. POJ 2723 Get Luffy Out

好题！

题意：
有个地牢有 m 层，所谓地牢，当然只有你通过了 d 层才能进入 d+1 层。每一层都有一扇大门，只有打开它才能进入下一层，每一扇大门有两把锁，只要你打开一种一扇就能打开这扇大门。而我们有 n 串钥匙，一串2把 ，一旦使用了其中一把，另一把就会消失。问最深能进入多少层。

思路：
数据不是很大，不二分也都可以过。

对于一道 2-SAT 题，我们最主要的是要抓住它的矛盾所在。对于一扇门，两把锁，如果我们要打开它，就必须有一把钥匙存在。换言之，打开这扇门 与 这扇门上的两把钥匙都不存在 矛盾！

假设锁 X,Y 对应 钥匙 x,y , 建边 ~x -> y ，~y -> x

这里不得不感慨 2-SAT 的逻辑性之强，我自己实在是一时间没有想到，就看题解去了。而这里最妙的地方并不是在这里。这道题是我第一道（微小地）跳出模板的题。

上面刚说了， 2-SAT 的重点就是抓住它的矛盾所在，以往的题，两个矛盾相对都是自己决定的，而这题却是题目给定的。详细的看 judge 函数。

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

using namespace std;
const int maxn = 10005;

int idx, n, m, scc, top, vis_time;
int head[maxn], dfn[maxn], low[maxn], color[maxn], st[maxn];
bool instack[maxn];
int refer[maxn], a[maxn], b[maxn];
int key[maxn][2];

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

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;
        dfn[i] = -1;
        instack[i] = false;
    }
    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(int mid)
{
    int u, v;
    init();
    for (int i = 0; i < mid; i++) {
        u = a[i], v = b[i];
        addEdge(refer[u], v);
        addEdge(refer[v], u);
    }
    for (int i = 0; i < (n << 1); i++)
        if (dfn[i] == -1)
            tarjan(i);
    for (int i = 0; i < n; i++)
        if (color[i] == color[refer[i]]) //看这里！！
            return false;
    return true;
}

int main()
{
    int u, v;
    while (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0)
            break;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &u, &v);
            refer[u] = v;
            refer[v] = u;
        }
        for (int i = 0; i < m; i++)
            scanf("%d %d", a + i, b + i);
        int le = 0, ri = m, mid;
        while (le <= ri) {
            mid = (le + ri) >> 1;
            if (judge(mid))
                le = mid + 1;
            else
                ri = mid - 1;
        }
        printf("%d\n", le - 1);
    }
    return 0;
}

10. HDU 1816 Get Luffy Out *

Share