题意：
给你两个总部，s1 ,s2,和n个点，任意两点之间都是通过这个总部相连的，其中有一些点不能连在同一个总部上，有一些点可以连接在同一个总部上，总部和总部之间可以直接连接，就是假如a,b相连，可以使这样四中情况中的一种
a-s1 s1 - b
a-s2 s2 - b
a-s1 s1 - s2 s2 - b
a-s2 s2 - s1 s1 - b
最后问你任意ab距离最远的最近是多少。
思路：
首先这个题目的总部有两个，还有一些限制关系，那么很容易就想到2sat问题，关键是怎么建边，怎样找到限制关系，还是举例子说容易懂，
s_x1[i] : 表示i点到S1的距离。
s_x2[i] : 表示i点到S2的距离。
D 表示S1,S2的距离。
彼此厌恶 x -> ~y ,y -> ~x ,~y -> x ,~x -> y
彼此喜欢 x -> y ,~x -> ~y ,y -> x ,~y -> ~x
s_x1[x] + s_x1[y] > mid x -> ~y ,y -> ~x
s_x2[x] + s_x2[y] > mid ~x -> y ,~y -> x
s_x1[x] + s_x2[y] + D > mid x -> y ,~y -> ~x
s_x2[x] + s_x1[y] + D > mid ~x -> ~y ,y -> x
每次二分就这么建边就ok了，还有提示下，之前在网上看到有个人的题解是直接先跑了便彼此厌恶和喜欢的，然后二分的时候就不管那个了，那个我感觉正确性说不通，我是每次都全部从新建边的，上面的如果写错了请大家留言指教，互相学习。
#include<stdio.h>
#include<string.h>
#include<stack> #define N_node 1000 + 10
#define N_edge 5000000 + 300
using namespace std; typedef struct
{
int to ,next;
}STAR; typedef struct
{
int x ,y;
}NODE; STAR E1[N_edge] ,E2[N_edge];
NODE S1 ,S2 ,A;
int s_x1[550] ,s_x2[550];
int list1[N_node] ,list2[N_node] ,tot;
int Belong[N_node] ,cnt;
int mark[N_node];
int F[1100][2] ,NF[1100][2];
stack<int>st; void add(int a ,int b)
{
E1[++tot].to = b;
E1[tot].next = list1[a];
list1[a] = tot; E2[tot].to = a;
E2[tot].next = list2[b];
list2[b] = tot;
} void DFS1(int s)
{
mark[s] = 1;
for(int k = list1[s] ;k ;k = E1[k].next)
if(!mark[E1[k].to]) DFS1(E1[k].to);
st.push(s);
} void DFS2(int s)
{
mark[s] = 1;
Belong[s] = cnt;
for(int k = list2[s] ;k ;k = E2[k].next)
if(!mark[E2[k].to]) DFS2(E2[k].to);
} int abss(int x)
{
return x > 0 ? x : -x;
} int dis(NODE a ,NODE b)
{
return abss(a.x - b.x) + abss(a.y - b.y);
} bool ok(int mid ,int n ,int m ,int q)
{
memset(list1 ,0 ,sizeof(list1));
memset(list2 ,0 ,sizeof(list2));
tot = 1;
for(int i = 1 ;i <= m ;i ++)
{
int x = NF[i][0] * 2 ,xx = NF[i][0] * 2 + 1;
int y = NF[i][1] * 2 ,yy = NF[i][1] * 2 + 1;
add(x ,yy) ,add(y ,xx);
add(yy ,x) ,add(xx ,y);
}
for(int i = 1 ;i <= q ;i ++)
{
int x = F[i][0] * 2 ,xx = F[i][0] * 2 + 1;
int y = F[i][1] * 2 ,yy = F[i][1] * 2 + 1;
add(x ,y) ,add(xx ,yy);
add(y ,x) ,add(yy ,xx);
}
int D = dis(S1 ,S2);
for(int i = 0 ;i < n ;i ++)
for(int j = i + 1 ;j < n ;j ++)
{
int x = i * 2 ,xx = i * 2 + 1;
int y = j * 2 ,yy = j * 2 + 1;
if(s_x1[i] + s_x1[j] > mid) add(x ,yy) ,add(y ,xx);
if(s_x2[i] + s_x2[j] > mid) add(xx ,y) ,add(yy ,x);
if(s_x1[i] + s_x2[j] + D > mid) add(x ,y) ,add(yy ,xx);
if(s_x2[i] + s_x1[j] + D > mid) add(xx ,yy) ,add(y ,x);
}
memset(mark ,0 ,sizeof(mark));
while(!st.empty()) st.pop();
for(int i = 0 ;i < n * 2 ;i ++)
if(!mark[i]) DFS1(i);
memset(mark ,0 ,sizeof(mark));
cnt = 0;
while(!st.empty())
{
int xin = st.top();
st.pop();
if(mark[xin]) continue;
++ cnt;
DFS2(xin);
}
int mk = 0;
for(int i = 0 ;i < n * 2 && !mk;i += 2)
if(Belong[i] == Belong[i^1]) mk = 1;
return !mk;
} int main ()
{
int n ,m ,q;
int i ,low ,mid ,up;
while(~scanf("%d %d %d" ,&n ,&m ,&q))
{
scanf("%d %d %d %d" ,&S1.x ,&S1.y ,&S2.x ,&S2.y);
low = up = 8000000;
for(i = 0 ;i < n ;i ++)
{
scanf("%d %d" ,&A.x ,&A.y);
s_x1[i] = dis(A ,S1);
s_x2[i] = dis(A ,S2);
if(low > s_x1[i]) low = s_x1[i];
if(low > s_x2[i]) low = s_x2[i];
}
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d" ,&NF[i][0] ,&NF[i][1]);
NF[i][0] -- ,NF[i][1] --;
}
for(i = 1 ;i <= q ;i ++)
{
scanf("%d %d" ,&F[i][0] ,&F[i][1]);
F[i][0] -- ,F[i][1] -- ;
}
int ans = -1;
while(low <= up)
{
mid = (low + up) >> 1;
if(ok(mid ,n ,m ,q))
ans = mid ,up = mid - 1;
else low = mid + 1;
}
printf("%d\n" ,ans);
}
return 0;
}