思路：首先将hate和friend建边求其次2-SAT问题，判断是否能有解，没解就输出-1，否则用二分枚举最大的长度，将两个barn的距离小于mid的看做是矛盾，然后建边，求2-SAT问题。找出最优解。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #define Maxn 3010 #define Maxm 1000000 using namespace std; int dfn[Maxn],low[Maxn],vi[Maxn],head[Maxn],e,n,m,lab,top,Stack[Maxn],num,id[Maxn],A,B,ss; struct Edge{ int u,v,next,l; }edge[Maxm]; struct Point{ int x,y; }p[Maxn],s1,s2; struct Match{ int a,b; }hate[Maxn],Friend[Maxn]; void init() { int i,j; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(head,-1,sizeof(head)); memset(id,0,sizeof(id)); memset(vi,0,sizeof(vi)); e=lab=num=top=0; } void add(int u,int v) { edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++; } int Dis(Point a,Point b) { return abs(a.x-b.x)+abs(a.y-b.y); } void Tarjan(int u) { int i,j,v; dfn[u]=low[u]=++lab; Stack[top++]=u; vi[u]=1; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].v; if(!dfn[v]) { Tarjan(v); low[u]=min(low[u],low[v]); } if(vi[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { ++num; do{ i=Stack[--top]; vi[i]=0; id[i]=num; }while(i!=u); } } void build(int mid) { int i,j; init(); for(i=1;i<=n;i++) for(j=1;j<=n;j++){ if(j==i) continue; if(Dis(p[i],s1)+Dis(p[j],s1)>mid) { add(i,j+n); add(j,i+n); } if(Dis(p[i],s2)+Dis(p[j],s2)>mid) { add(i+n,j); add(j+n,i); } if(Dis(p[i],s1)+Dis(p[j],s2)+ss>mid) { add(i,j); add(j+n,i+n); } if(Dis(p[i],s2)+Dis(p[j],s1)+ss>mid) { add(j,i); add(i+n,j+n); } } for(i=1;i<=A;i++) { add(hate[i].a,hate[i].b+n); add(hate[i].b,hate[i].a+n); add(hate[i].a+n,hate[i].b); add(hate[i].b+n,hate[i].a); } for(i=1;i<=B;i++) { add(Friend[i].a,Friend[i].b); add(Friend[i].a+n,Friend[i].b+n); add(Friend[i].b,Friend[i].a); add(Friend[i].b+n,Friend[i].a+n); } } int cal() { int i; for(i=1;i<=n*2;i++) { if(!dfn[i]) Tarjan(i); } for(i=1;i<=n;i++) { if(id[i]==id[i+n]) return 0; } return 1; } int solve() { int i,j; for(i=1;i<=A;i++) { add(hate[i].a,hate[i].b+n); add(hate[i].b,hate[i].a+n); add(hate[i].a+n,hate[i].b); add(hate[i].b+n,hate[i].a); } for(i=1;i<=B;i++) { add(Friend[i].a,Friend[i].b); add(Friend[i].a+n,Friend[i].b+n); add(Friend[i].b,Friend[i].a); add(Friend[i].b+n,Friend[i].a+n); } if(!cal()) return -1; int l,r,mid; l=0;r=4000010; while(l+1<r) { mid=(l+r)>>1; build(mid); if(cal()) r=mid; else l=mid; } return r; } int main() { int i,j,a,b,c; while(scanf("%d%d%d",&n,&A,&B)!=EOF) { init(); scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y); for(i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); for(i=1;i<=A;i++) scanf("%d%d",&hate[i].a,&hate[i].b); for(i=1;i<=B;i++) scanf("%d%d",&Friend[i].a,&Friend[i].b); ss=Dis(s1,s2); printf("%d ",solve()); } return 0; }