题意
有 N 个牛栏，现在通过一条通道（s1,s2）要么连到s1，要么连到s2，把他们连起来，他们之间有一些约束关系，一些牛栏不能连在同一个点，一些牛栏必须连在同一个点，现在问有没有可能把他们都连好，而且满足所有的约束关系，如果可以，输出距离最大的两个牛栏之间距离最小值（两点距离是指哈密顿距离）
Sol
二分答案+(2-SAT)判定
每次二分答案，把枚举两个点距离(>mid)的就连边限制
傻逼到没输出-1，WA无数遍
# include <iostream>
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <math.h>
# include <algorithm>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1005);
const int __(4e6 + 5);
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
int n, A, B, tmp, first[_], cnt, num, mx, mn = 2e9;
int x[_], y[_], X1, Y1, X2, Y2, d1[_], d2[_], dis;
int S[_], vis[_], dfn[_], low[_], Index, col[_];
struct Link{
int u, v;
} hate[_], like[_];
struct Edge{
int to, next;
} edge[__];
IL void Add(RG int u, RG int v){
edge[cnt] = (Edge){v, first[u]}; first[u] = cnt++;
}
IL void Tarjan(RG int u){
vis[u] = 1, dfn[u] = low[u] = ++Index, S[++S[0]] = u;
for(RG int e = first[u]; e != -1; e = edge[e].next){
RG int v = edge[e].to;
if(!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] != low[u]) return;
RG int v = S[S[0]--]; col[v] = ++num, vis[v] = 0;
while(v != u) v = S[S[0]--], col[v] = num, vis[v] = 0;
}
IL int Calc(RG int a, RG int b, RG int c, RG int d){
return abs(a - c) + abs(b - d);
}
IL int Check(RG int mid){
Fill(first, -1), Fill(dfn, 0), Fill(col, 0), cnt = Index = num = 0;
for(RG int i = 1; i <= A; ++i){
Add(hate[i].u, hate[i].v + n), Add(hate[i].u + n, hate[i].v);
Add(hate[i].v, hate[i].u + n), Add(hate[i].v + n, hate[i].u);
}
for(RG int i = 1; i <= B; ++i){
Add(like[i].u, like[i].v), Add(like[i].u + n, like[i].v + n);
Add(like[i].v, like[i].u), Add(like[i].v + n, like[i].u + n);
}
for(RG int i = 1; i < n; ++i)
for(RG int j = i + 1; j <= n; ++j){
if(d1[i] + d1[j] > mid) Add(i, j + n), Add(j, i + n);
if(d2[i] + d2[j] > mid) Add(i + n, j), Add(j + n, i);
if(d1[i] + dis + d2[j] > mid) Add(i, j), Add(j + n, i + n);
if(d2[i] + dis + d1[j] > mid) Add(i + n, j + n), Add(j, i);
}
for(RG int tmp = n << 1, i = 1; i <= tmp; ++i) if(!dfn[i]) Tarjan(i);
for(RG int i = 1; i <= n; ++i) if(col[i] == col[i + n]) return 0;
return 1;
}
int main(RG int argc, RG char* argv[]){
n = Input(), A = Input(), B = Input();
X1 = Input(), Y1 = Input(), X2 = Input(), Y2 = Input();
dis = Calc(X1, Y1, X2, Y2);
for(RG int i = 1; i <= n; ++i){
x[i] = Input(), y[i] = Input();
d1[i] = Calc(x[i], y[i], X1, Y1);
d2[i] = Calc(x[i], y[i], X2, Y2);
mx = max(mx, max(d1[i], d2[i]));
mn = min(mn, min(d1[i], d2[i]));
}
for(RG int i = 1; i <= A; ++i) hate[i] = (Link){Input(), Input()};
for(RG int i = 1; i <= B; ++i) like[i] = (Link){Input(), Input()};
mx = mx * 2 + dis, mn *= 2;
RG int l = mn, r = mx, ans = -1;
while(l <= r){
RG int mid = (l + r) >> 1;
if(Check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
printf("%d
", ans);
return 0;
}