算法：poj 2749 & hdu 1815 Building roads（2-SAT + 二分，好题）

算法：poj 2749 & hdu 1815 Building roads（2-SAT + 二分，好题）2014-01-10 csdn shuangde800【题目大意】

有n个牛棚，还有两个中转站S1和S2， S1和S2用一条路连接起来。为了使得任意牛棚两个都可以有道路联通，现在要让每个牛棚都连接一条路到S1或者S2。

有a对牛棚互相有仇恨，所以不能让他们的路连接到同一个中转站。还有b对牛棚互相喜欢，所以他们的路必须连到同一个中专站。

道路的长度是两点的曼哈顿距离。

问最小的任意两牛棚间的距离中的最大值是多少？

【思路】

两天前看了这题，当时没什么想法，今天又翻看了一下，想出来了。

每个牛棚有可以选择S1或者S2，并且有矛盾对，是2-SAT无疑。

首先这题要二分所求的距离是一定要的，最大的问题是怎样建图？

我们枚举了任意牛棚之间的最大距离，说明如果有两个牛棚，他们选择的连接方式使得他们的距离大于最大距离，他们肯定就不能选择这种连接的，这是个矛盾对，根据这个可以加边了。

然后就是互相仇恨的和互相喜欢的建边，这个很容易想到。

写完后在poj提交，发现 WA了，但是很肯定自己的算法没问题，就想到可能是二分的右边界太小了，于是改大成了400W，然后AC了。

于是又交到hdu去，结果竟然TLE了。。。搞了很久，发现还是右边界开小了，于是不断加大，最后到800W才AC了。右边界小了会TLE，这个让我想不通了，求指教

另外，每一点到S1和S2的距离预先算好，而不是每次建图时都算，这样可以省很多很多的时间

【代码】

#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<cmath>using namespace std;const int MAXN = 1005;const int VN = MAXN*2;const int EN = 1200000;int n, hateNum, likeNum;int d[VN], sLen;struct Node{int x, y;}barn[MAXN], hate[VN], like[VN], s1, s2;struct Edge{int v, next;};struct Graph{int size, head[VN];Edge E[EN];void init（）{size=0; memset（head, -1, sizeof（head））; }void addEdge（int u, int v）{E[size].v = v;E[size].next = head[u];head[u] = size++;}}g;class Two_Sat{public:bool check（const Graph& g, const int n）{scc（g, 2*n）;for（int i=0; i<n; ++i）if（belong[i] == belong[i+n]）return false;return true;}private:void tarjan（const Graph& g, const int u）{int v; low[u] = DFN[u] = ++idx;sta[top++] = u;instack[u] = true;for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（DFN[v] == -1）{tarjan（g, v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）{low[u] = min（low[u], DFN[v]）;}}if（DFN[u] == low[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v]= bcnt;}while（u ！= v）;}}void scc（const Graph& g, const int n）{bcnt = idx = top = 0;memset（DFN, -1, sizeof（DFN））;memset（instack, 0, sizeof（instack））;for（int i=0; i<n; ++i）if（DFN[i] == -1）tarjan（g, i）;}private:int idx, top, bcnt;int DFN[VN], low[VN], belong[VN], sta[VN];bool instack[VN];}sat;inline int dist（const Node& a, const Node& b）{return abs（a.x-b.x）+abs（a.y-b.y）;}void buildGraph（int maxLen）{g.init（）; for（int i=0; i<n; ++i）for（int j=i+1; j<n; ++j）if（i！=j）{int l1=d[i], l2=d[i+n];int r1=d[j], r2=d[j+n];if（l1 + r1 > maxLen）{g.addEdge（i, j+n）;g.addEdge（j, i+n）;}if（l1 + r2 + sLen > maxLen）{g.addEdge（i, j）;g.addEdge（j+n, i+n）;}if（l2 + r1 + sLen > maxLen）{g.addEdge（i+n, j+n）;g.addEdge（j, i）;}if（l2 + r2 > maxLen）{g.addEdge（i+n, j）;g.addEdge（j+n, i）;}}for（int i=0; i<hateNum; ++i）{int a=hate[i].x, b=hate[i].y;g.addEdge（a, b+n）;g.addEdge（a+n, b）;g.addEdge（b, a+n）;g.addEdge（b+n, a）;}for（int i=0; i<likeNum; ++i）{int a=like[i].x, b=like[i].y;g.addEdge（a, b）;g.addEdge（a+n, b+n）;g.addEdge（b, a）;g.addEdge（b+n, a+n）;} }int main（）{while（~scanf（"%d%d%d", &n, &hateNum, &likeNum））{scanf（"%d%d%d%d", &s1.x,&s1.y,&s2.x,&s2.y）;sLen = dist（s1, s2）;for（int i=0; i<n; ++i）{scanf（"%d%d", &barn[i].x, &barn[i].y）;d[i] = dist（barn[i], s1）;d[i+n] = dist（barn[i], s2）;}for（int i=0; i<hateNum; ++i）{scanf（"%d%d", &hate[i].x, &hate[i].y）;--hate[i].x;--hate[i].y;}for（int i=0; i<likeNum; ++i）{scanf（"%d%d", &like[i].x, &like[i].y）;--like[i].x;--like[i].y;}int l=0, r=8000000, mid, ans=-1;while（l <= r）{mid = （l+r）>>1;buildGraph（mid）;if（sat.check（g, n））{ans = mid;r = mid-1;} elsel = mid+1;}printf（"%d
", ans）;}return 0;}