给你两个总部，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 -> xs_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 " ,ans); } return 0; }