POJ 2749 Building roads 题解《挑战程序设计竞赛》

POJ 2749 Building roads 

阳关路与独木桥：有N个农场，其中A对相互讨厌，不能碰面；B对相互喜欢，必须碰面。给定两个中转站S1和S2、各个农场的坐标，让每个农场连接到其中一个中转站。求最小化任意两个农场通过中转站的最大距离，若无法实现，输出-1。

4.3成为图论大师之路 

2-SAT

N个农场分别有2N个节点，对第i个农场而言，节点2*i+k表示连接到第k个中转站，则节点2*i+1-k表示连接到另一个中转站，为了表述方便，定义事件i和事件j表示i和j通过中转站k。

给定一个最大距离d，对i和j两个农场，若通过同一个中转站连接它们的距离大于d，则说明i and j = 0，于是按照公式

A AND B = 0     <=>      A->!B     &&  B->!A

得到蕴涵表达式，并连接相应的节点。

若通过不同的中转站连接，距离大于d，则说明i and !j = 0，也连接相应节点。

对于相互讨厌的i和j，有i xor j = 1；对于相互喜欢的i和j，有i xor j = 0，参考POJ 3678 Katu Puzzle 题解《挑战程序设计竞赛》连接节点。

对于以上所有逻辑表达式，遍历两个k，构图，scc即可。

而对于题目所求的最小化最大值，依然是二分解决。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX_N 500
#define MAX_V 2 * MAX_N

int V;                      // 顶点数
vector<int> G[MAX_V];       // 图的邻接表表示
vector<int> rG[MAX_V];      // 反向图
vector<int> vs;             // 后序遍历顺序的顶点列表
bool used[MAX_V];           // 访问标记
int cmp[MAX_V];             // 所属强连通分量的拓补序

void add_edge(const int &from, const int &to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(const int &v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); ++i)
    {
        if (!used[G[v][i]])
            dfs(G[v][i]);
    }
    vs.push_back(v);
}

void rdfs(const int &v, const int &k)
{
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!used[rG[v][i]])
            rdfs(rG[v][i], k);
    }
}

int scc()
{
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int v = 0; v < V; ++v)
    {
        if (!used[v])
            dfs(v);
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i)
    {
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    }

    return k;
}

//////////////////////////////////////////////////////////////
int N, A, B;
int Sy[2], Sx[2];
int ys[MAX_N], xs[MAX_N];
int dist;

int dists[MAX_N][2];
int hates[MAX_V][2], likes[MAX_V][2];

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

bool check(const int &d)
{
    for (int i = 0; i < V; ++i)
    {
        G[i].clear();
        rG[i].clear();
    }

    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
            for (int k = 0; k < 2; ++k)
            {// A AND B = 0    <=>      A->!B     &&  B->!A
                if (dists[i][k] + dists[j][k] > d)// i 和 j连到同一个中转站
                {// i and j = 0
                    add_edge(2 * i + k, 2 * j + 1 - k);// i -> !j
                    add_edge(2 * j + k, 2 * i + 1 - k);// j -> !i
                }
                if (dists[i][k] + dists[j][1 - k] + dist > d)// 不同中转站
                {// i and !j = 0
                    add_edge(2 * i + k, 2 * j + k);         // i -> j
                    add_edge(2 * j + 1 - k, 2 * i + 1 - k); // !j -> !i
                }
            }
        }
    }

    for (int i = 0; i < A; ++i)
    {
        for (int k = 0; k < 2; ++k)
        {
            add_edge(2 * hates[i][0] + k, 2 * hates[i][1] + 1 - k);
            add_edge(2 * hates[i][1] + k, 2 * hates[i][0] + 1 - k);
        }
    }

    for (int i = 0; i < B; ++i)
    {
        for (int k = 0; k < 2; ++k)
        {
            add_edge(2 * likes[i][0] + k, 2 * likes[i][1] + k);
            add_edge(2 * likes[i][1] + 1 - k, 2 * likes[i][0] + 1 - k);
        }
    }

    scc();
    for (int i = 0; i < N; ++i)
    {
        if (cmp[2 * i + 0] == cmp[2 * i + 1])
        {
            return false;
        }
    }
    return true;
}

int solve()
{
    V = 2 * N;
    dist = manhattan_distance(Sx[0], Sy[0], Sx[1], Sy[1]);
    for (int i = 0; i < N; ++i)
    {
        for (int k = 0; k < 2; ++k)
        {
            dists[i][k] = manhattan_distance(xs[i], ys[i], Sx[k], Sy[k]);
        }
    }

    int max_dist = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
            for (int k = 0; k < 2; ++k)
            {
                max_dist = max(max_dist, dists[i][k] + dists[j][k]);
                max_dist = max(max_dist, dists[i][k] + dists[j][1 - k] + dist);
            }
        }
    }
    ++max_dist;
    int low = -1, high = max_dist;
    while (high - low > 1)
    {
        const int mid = (high + low) >> 1;
        (check(mid) ? high : low) = mid;
    }
    return high == max_dist ? -1 : high;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d%d", &N, &A, &B);
    for (int i = 0; i < 2; ++i)
    {
        scanf("%d%d", Sx + i, Sy + i);
    }
    for (int i = 0; i < N; ++i)
    {
        scanf("%d%d", xs + i, ys + i);
    }
    for (int i = 0; i < A; ++i)
    {
        for (int k = 0; k < 2; ++k)
        {
            scanf("%d", hates[i] + k);
            --hates[i][k];
        }
    }
    for (int i = 0; i < B; ++i)
    {
        for (int k = 0; k < 2; ++k)
        {
            scanf("%d", likes[i] + k);
            --likes[i][k];
        }
    }
    printf("%d\n", solve());
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

Reference

http://d.hatena.ne.jp/komiyam/20121016/1350387024

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2749 Building roads 题解《挑战程序设计竞赛》