poj 六道2-sat最后一题第六题：

题目描述：有n个农场，每个农场有坐标x，y。

有两个集合点s1和s2（也有坐标），每个农场必须连接其中的一个（有且仅有一个）。

然后有A个条件，每个条件a，b表示a农场不能和b农场连接在一个集合点。

然后再有B个条件，每个条件a，b表示a农场必须和b农场连接在一个集合点。

问你，在各种合法的连接情况中，任何两个农场间的距离的最大值的最小值是多少。

解题报告：

每个农场i分成两个点，i和i + n，前面表示连接左侧集合点，后面的表示连接右侧集合点。

对于条件A中的ab，连接

<a, b + n> <a + n, b> <b, a + n> <b + n, a>

这样就保证了ab不再一个集合点。同理，B条件也很好写。

然后就是用二分枚举答案（距离的最大值）。

对于每一次枚举的答案key，枚举任意两个农场a,b, 如果他俩的4种距离（a->s1->s1>b, a->s2->s2->b, a->s1->s2->b, a->s2->s1->b)有大于key的，就加入判定条件，不能这样连接。

这个key能够成功，二分右边界等于mid - 1，否则，左边界等于mid + 1.

代码如下：

#include<iostream>
#include<cmath>
using namespace std;
#define size 2000
int v[size], cnt;
struct edge{int to, next;} e[1000000];
void insert(int from, int to)
{
    e[cnt].to = to;
    e[cnt].next = v[from];//每次都插入到最前面
    v[from] = cnt++;
}
int belong[size], num[size], cntnum;
int dfn[size], low[size], index, instack[size], sta[size], top;
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    int tmp = v[id];
    while(tmp != -1)
    {
        if (!dfn[e[tmp].to])
        {
            tarjan(e[tmp].to);
            if (low[e[tmp].to] < low[id]) low[id] = low[e[tmp].to];
        }
        else if (instack[e[tmp].to] && dfn[e[tmp].to] < low[id])
            low[id] = dfn[e[tmp].to];
        tmp = e[tmp].next;
    }
    if (dfn[id] == low[id])
    {
        do
        {
            tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = cntnum;
            num[cntnum]++;
        }while(tmp != id);
        cntnum++;
    }
}

struct pint{int x, y;} vv[size], s[2];
int n ,a, b, e1[size][2], e2[size][2], Min, Max, slen;
int len(int id1, int id2){return abs(vv[id1].x - s[id2].x) + abs(vv[id1].y - s[id2].y);}
bool judge(int key)
{
    memset(v, -1, sizeof(v)); cnt = 0;
    for(int i = 0; i < a; i++)
    {
        insert(e1[i][0], e1[i][1] + n);insert(e1[i][0] + n, e1[i][1]);
        insert(e1[i][1], e1[i][0] + n);insert(e1[i][1] + n, e1[i][0]);
    }
    for(int i = 0; i < b; i++)
    {
        insert(e2[i][0], e2[i][1]);insert(e2[i][0] + n, e2[i][1] + n);
        insert(e2[i][1], e2[i][0]);insert(e2[i][1] + n, e2[i][0] + n);
    }
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
        {
            if (len(i, 0) + len(j, 0) > key)
                insert(i, j + n), insert(j, i + n);
            if (len(i, 1) + len(j, 1) > key)
                insert(i + n, j), insert(j + n, i);
            if (len(i, 0) + len(j, 1) + slen > key)
                insert(i, j), insert(j + n, i + n);
            if (len(i, 1) + len(j, 0) + slen > key)
                insert(i + n, j + n), insert(j, i);
        }
    index = top = cntnum = 0;
    memset(num, 0, sizeof(num));memset(dfn, 0, sizeof(dfn));
    for(int i = 1; i <= n + n; i++) if (!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; i++)
        if (belong[i] == belong[i + n]) return false;
    return true;
}
int main()
{
    scanf("%d%d%d", &n ,&a, &b); Min = 0x7fffffff, Max = -1;
    scanf("%d%d", &s[0].x, &s[0].y);
    scanf("%d%d", &s[1].x, &s[1].y);
    slen = abs(s[0].x - s[1].x) + abs(s[0].y - s[1].y);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &vv[i].x, &vv[i].y);
        if (len(i, 0) < Min) Min = len(i, 0);if (len(i, 1) < Min) Min = len(i, 1);
        if (len(i, 0) > Max) Max = len(i, 0);if (len(i, 1) > Max) Max = len(i, 1);
    }
    for(int i = 0; i < a; i++) scanf("%d%d", &e1[i][0], &e1[i][1]);
    for(int i = 0; i < b; i++) scanf("%d%d", &e2[i][0], &e2[i][1]);
    int l = Min * 2, r = Max * 2 + slen, ans = 0x7fffffff;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if (judge(mid)) {r = mid - 1; if (mid < ans) ans = mid;}
        else l = mid + 1;
    }
    if (ans == 0x7fffffff) printf("-1\n");
    else printf("%d\n", ans);
    return 0;
}