POJ 2749--Building roads（2-SAT）

题意：John有n个牛棚，每个牛棚都住着一些牛，这些牛喜欢串门（drop around，学到了。。。），所以John想要建几条路把他们连接起来。他选择的方法是建两个相连中转站，然后每个牛棚连接其中一个中转站就好啦。现在的问题是有一些牛相互憎恨，所以不能连同一个中转站，而又有一些牛相互喜欢，必须连同一个中转站（再次感叹，人不如牛。。），现在要你来建边，要求，任意两个牛棚的距离的最大距离最短。两点距离是指哈密顿距离。比如u, v连的是同一个中转站s1，距离就是dis(u,s1)+dis(v,s1) 如果连不同的中转站就是dis(u,s1)+dis(v,s2)+dis(u,v)，题意真的好不清楚啊

输入就是每个牛棚的坐标的中转站的坐标，已经牛之间的憎恨和喜欢关系。

输出最小距离。不能输出-1。

题解：二分。。。然后符合要求的边建图，2-sat求解。建图时喜欢和讨厌都要建四条边，仔细读题。。。仔细建边。。。

//我真的想吐槽我以前用的输入挂啊，我特么从哪搞来的辣鸡读入。。。用一次错一次。。。。

这套题做的我心真累。。。没有特别难的。。。但是每一道都wa的想死。。。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <bitset>

#include <cstdio>

#include <queue>

#include <stack>

#include <cmath>

#include <list>

#include <map>

#include <set>

#define pk(x) printf("%d\n", x)

using namespace std;

#define PI acos(-1.0)

#define EPS 1E-6

#define clr(x,c) memset(x,c,sizeof(x))

typedef long long ll;

const int N = ;

const int M = ;

inline int Scan()

{

    char ch = getchar();

    int data = ;

    while (ch < '' || ch > '') ch = getchar();

    do {

        data = data* + ch-'';

        ch = getchar();

    } while (ch >= '' && ch <= '');

    return data;

}

struct Edge {

    int from, to, next;

} edge[M];

int head[N];

int cntE;

void addedge(int u, int v) {

    edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++;

}

int dfn[N], low[N], idx;

int stk[N], top;

int in[N];

int kind[N], cnt;

void tarjan(int u)

{

    dfn[u] = low[u] = ++idx;

    in[u] = true;

    stk[++top] = u;

    for (int i = head[u]; i != -; i = edge[i].next) {

        int v = edge[i].to;

        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);

        else if (in[v]) low[u] = min(low[u], dfn[v]);

    }

    if (low[u] == dfn[u]) {

        ++cnt;

        while () {

            int v = stk[top--]; kind[v] = cnt; in[v] = false;

            if (v == u) break;

        }

    }

}

void init() {

    cntE = ;

    memset(head, -, sizeof head);

    memset(dfn, , sizeof dfn);

    memset(in, false, sizeof in);

    idx = top = cnt = ;

}

int ax[N], ay[N];

int bx[N], by[N];

int dis1[N], dis2[N];

int n, a, b;

int dis;

int cal(int x1, int y1, int x2, int y2) {

    return abs(x1-x2) + abs(y1-y2);

}

bool ok(int x) {

    init();

    for (int i = ; i <= n; ++i) {

        for (int j = i+; j <= n; ++j) {

            if (dis1[i] + dis1[j] > x) addedge(i, n+j), addedge(j, n+i);

            if (dis2[i] + dis2[j] > x) addedge(i+n, j), addedge(j+n, i);

            if (dis1[i] + dis2[j] + dis > x) addedge(i, j), addedge(j+n, i+n);

            if (dis2[i] + dis1[j] + dis > x) addedge(i+n, j+n), addedge(j, i);

        }

    }

    for (int i = ; i < a; ++i) {

        addedge(ax[i], ay[i] + n), addedge(ay[i] + n, ax[i]);

        addedge(ay[i], ax[i] + n), addedge(ax[i] + n, ay[i]);

    }

    for (int i = ; i < b; ++i) {

        addedge(bx[i], by[i]), addedge(by[i], bx[i]);

        addedge(bx[i] + n, by[i] + n), addedge(by[i] + n, bx[i] + n);

    }

    for (int i = ; i <= *n; ++i) if (!dfn[i]) tarjan(i);

    for (int i = ; i <= n; i++) if (kind[i] == kind[i + n]) return false;

    return true;

}

int main() {

    int x1, y1, x2, y2;

    int x, y;

    while (~scanf("%d%d%d", &n, &a, &b)) {

        x1 = Scan(); y1 = Scan(); x2 = Scan(); y2 = Scan();

        dis = cal(x1, y1, x2, y2);

        int maxn = ;

        for (int i = ; i <= n; ++i) {

            x = Scan(); y = Scan();

            dis1[i] = cal(x, y, x1, y1);

            dis2[i] = cal(x, y, x2, y2);

            maxn = max(maxn, max(dis1[i], dis2[i]));

        }

        maxn = maxn *  + dis;

        for (int i = ; i < a; ++i) ax[i] = Scan(), ay[i] = Scan();

        for (int i = ; i < b; ++i) bx[i] = Scan(), by[i] = Scan();

        int l = , r = maxn;

        int ans = -;

        while (l <= r) {

            int mid = (l+r) >> ;

            if (ok(mid)) ans = mid, r = mid - ;

            else l = mid + ;

        }

        printf("%d\n", ans);

    }

    return ;

}

巴特西

POJ 2749--Building roads（2-SAT）

最新文章

热门文章