2-SAT

URAL 1382 Game with Cards

Posted on

Table of contents

题解

2-SAT 一眼题,但是很遗憾,我之前刷的专题里面没有输出可行解的题。我不知道怎么输出可行解,我个人以为,只要染色数量等于点数就是可行解。有哪里不对的么??

但我至少认可了Yasola巨巨在挑程上说的拓扑排序输出可行解的说法。

传送门

题意
有n个人手中有n张卡,每个人说两句话,有一句必定为真,有一句必定为假。说了2-sat一眼题……
两句话分别说,我自己手上是几号卡,别人手上是几号卡,保证不存在相同的陈述。

思路:
对于每两个人 i 和 j 的陈述,进行判断,如果产生矛盾,则建边。

产生矛盾是指两个的陈述,主语或者谓语有一个不同就产生了矛盾。
eg
1 号 手中有 2 号卡 < ---- > 1 号手中有 3 号卡
1 号 手中有 2 号卡 < ---- > 2 号手中有 2 号卡

两人的陈述分别是

陈述12
ai -> a[i]b[i] -> c[i]
bj -> a[j]b[j] -> c[j]

建边方式如下 a 表示 a 的 1 语句是对的 ,~a 表示 a 的 2 语句是对的

矛盾建边a1a2
b1a -> ~b , b -> ~a~a -> ~ b , b -> a
b2a -> b , ~b -> ~a~a -> b , ~b -> a

根据Yasola巨巨所说,求2-sat应该有三个常用算法

  1. 暴力法
  2. Tarjan
  3. Kosaraju

第三种算法昨天才知道,现在还没学,先贴上 1 和 2 的AC Code

暴力法

#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, vis_time, top;
int head[maxn], st[maxn];
bool instack[maxn], vis[maxn];
int a[maxn], b[maxn], c[maxn], num[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;
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

bool dfs(int u)
{
    if (vis[u ^ 1])
        return false;
    if (vis[u])
        return true;
    vis[u] = true;
    st[top++] = u;
    for (int id = head[u]; ~id; id = edges[id].nxt)
        if (!dfs(edges[id].to))
            return false;
    return true;
}

bool solve()
{
    for (int i = 0; i < 2 * n; i += 2) {
        if (!vis[i] && !vis[i + 1]) {
            top = 0;
            if (!dfs(i)) {
                while (top)
                    vis[st[--top]] = false;
                if (!dfs(i + 1))
                    return false;
            }
        }
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    if (solve())
        for (int i = 0; i < n; i++)
            printf("%d ", vis[i << 1] ? 1 : 2);
    return 0;
}

Tarjan

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

using namespace std;

const int maxn = 2005;

int idx, tpidx, n, m, scc, top, vis_time;
int head[maxn], tphead[maxn], dfn[maxn], low[maxn], in[maxn], color[maxn], st[maxn];
bool instack[maxn], vis[maxn], judge[maxn];
int a[maxn], b[maxn], c[maxn], indegree[maxn];
int crs[maxn], col[maxn];

queue<int> que;

struct node {
    int from, to;
    int next;
} edges[1005 * 1005 * 2], tp_edges[1005 * 1005 * 2];

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

void addTPEdge(int u, int v)
{
    tp_edges[tpidx].from = u;
    tp_edges[tpidx].to = v;
    tp_edges[tpidx].next = tphead[u];
    tphead[u] = tpidx++;
}

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].next) {
        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);
    }
}

void CreateGraph()
{
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] == a[j]) {
                addEdge(i << 1, j << 1 | 1);
                addEdge(j << 1, i << 1 | 1);
            }
            if (b[i] == b[j] || c[i] == c[j]) {
                addEdge(i << 1 | 1, j << 1);
                addEdge(j << 1 | 1, i << 1);
            }
            if (i + 1 == b[j] || a[i] == c[j]) {
                addEdge(i << 1, j << 1);
                addEdge(j << 1 | 1, i << 1 | 1);
            }
            if (b[i] == j + 1 || c[i] == a[j]) {
                addEdge(i << 1 | 1, j << 1 | 1);
                addEdge(j << 1, i << 1);
            }
        }
    }
}

void topoSort()
{
    for (int i = 1; i <= scc; i++)
        if (indegree[i] == 0)
            que.push(i);
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
        if (col[cur] == 0) {
            col[cur] = 1;
            col[crs[cur]] = -1;
        }
        for (int id = tphead[cur]; ~id; id = tp_edges[id].next)
            if (--indegree[tp_edges[id].to] == 0)
                que.push(tp_edges[id].to);
    }
}

bool getAns()
{
    for (int i = 0; i < n; i++) {
        if (color[i << 1] == color[i << 1 | 1])
            return false;
        crs[color[i << 1]] = color[i << 1 | 1];
        crs[color[i << 1 | 1]] = color[i << 1];
    }
    for (int i = 0; i < idx; i++) { 
        if (color[edges[i].from] != color[edges[i].to]) {
            addTPEdge(color[edges[i].to], color[edges[i].from]);
            indegree[color[edges[i].from]]++;
        }
    }
    topoSort();
    for (int i = 0; i < n; i++)
        judge[i] = col[color[i << 1]] == 1 ? true : false;
    return true;
}

void init()
{
    while (!que.empty())
        que.pop();
    for (int i = 0; i < 2 * n; i++)
        tphead[i] = head[i] = -1;
}

int main()
{
    scanf("%d", &n);
    init();
    for (int i = 0; i < n; i++)
        scanf("%d %d %d", a + i, b + i, c + i);
    CreateGraph();
    for (int i = 0; i < 2 * n; i++)
        if (dfn[i] == 0)
            tarjan(i);
    if (getAns())
        for (int i = 0; i < n; i++)
            printf("%d ", judge[i] ? 1 : 2);
    return 0;
}
2-SAT

2-SAT专题(3)

Posted on

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大都只是套模板而已。
2-SAT

2-SAT专题(2)

Posted on

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 *

2-SAT

2-SAT专题(1)

Posted on

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

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;
}