poj2749 Building roads

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

using namespace std;

const int maxn = 110010, maxm = 1100010;

int n, a, b,pre[maxn],low[maxn],scc[maxn],dfs_clock,top;
int hate[maxn][2], like[maxn][2], head[maxn], to[maxm], nextt[maxm], tot = 1;
int sx1, sy1, sx2, sy2,d,d1[maxn],ans,d2[maxn],top1,top2,r = 0,l = 0;

void add(int x, int y)
{
    to[tot] = y;
    nextt[tot] = head[x];
    head[x] = tot++;
}

int dis(int x1, int y1, int x2, int y2)
{
    return abs(x2 - x1) + abs(y2 - y1);
}

stack <int> s;

void tarjan(int u)
{
    pre[u] = low[u] = ++dfs_clock;
    s.push(u);
    for (int i = head[u]; i; i = nextt[i])
    {
        int v = to[i];
        if (!pre[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else
            if (!scc[v])
                low[u] = min(low[u], pre[v]);
    }
    if (pre[u] == low[u])
    {
        top++;
        while (1)
        {
            int t = s.top();
            s.pop();
            scc[t] = top;
            if (t == u)
                break;
        }
    }
}

bool check(int maxx)
{
    memset(head, 0, sizeof(head));
    tot = 1;
    memset(pre, 0, sizeof(pre));
    memset(scc, 0, sizeof(scc));
    memset(low, 0, sizeof(low));
    dfs_clock = 0;
    top = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
        if (d1[i] + d1[j] > maxx)
        {
            add(i, j + n);  //i在1号点j就必须在2号点
            add(j, i + n);
        }
        if (d2[i] + d2[j] > maxx)
        {
            add(i + n, j); //i在2号点j就必须在1号点
            add(j + n, i);
        }
        if (d1[i] + d2[j] + d > maxx)
        {
            add(i, j);   //i在1，j在2的时候不满足要求，那么当i在1的时候，j必须在1
            add(j + n, i + n);
        }
        if (d1[j] + d2[i] + d > maxx)
        {
            add(j, i); 
            add(i + n, j + n);
        }
        }
    for (int i = 1; i <= a; i++)
    {
        add(hate[i][0], hate[i][1] + n);
        add(hate[i][1] + n, hate[i][0]);
        add(hate[i][1], hate[i][0] + n);
        add(hate[i][0] + n, hate[i][1]);
    }
    for (int i = 1; i <= b; i++)
    {
        add(like[i][0], like[i][1]);
        add(like[i][1], like[i][0]);
        add(like[i][1] + n, like[i][0] + n);
        add(like[i][0] + n, like[i][1] + n);
    }
    for (int i = 1; i <= 2 * n; i++)
        if (!pre[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        if (scc[i] == scc[i + n])
            return false;
    return true;
}

int main()
{
    while (~scanf("%d%d%d", &n, &a, &b))
    {
        scanf("%d%d%d%d", &sx1, &sy1, &sx2, &sy2);
        d = dis(sx1, sy1, sx2, sy2);
        for (int i = 1; i <= n; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            d1[i] = dis(sx1, sy1, x, y);
            d2[i] = dis(sx2, sy2, x, y);
            r = max(r, max(d1[i], d2[i]));
        }
        r = r * 2 + d;
        for (int i = 1; i <= a; i++)
            scanf("%d%d", &hate[i][0], &hate[i][1]);
        for (int i = 1; i <= b; i++)
            scanf("%d%d", &like[i][0], &like[i][1]);
        ans = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (check(mid))
            {
                r = mid - 1;
                ans = mid;
            }
            else
                l = mid + 1;
        }
        printf("%d\n", ans);
    }

    return 0;
}