（这个约翰的奶牛真多事…………………………）
i表示u与s1连，i+n表示u与s2连。
老规矩，u到v表示取u必须取v。
那么对于互相打架的奶牛u，v，有：
add(u,v+n);add(v,u+n);
add(u+n,v);add(v+n,u);
对于互为朋友的奶牛u，v，有：
add(u,v);add(v,u);
add(u+n,v+n);add(v+n,u+n);
但这远远不够，我们需要求最大值最小……
二分？但是我们怎么边处理矛盾边的距离？
那么我们也想把连边处理成冲突。
对于奶牛i，j，sxy表示i到x到y到j的距离，mid是我们二分的最大值最小。
那么显然，对于s>mid，那么一定是矛盾的，此时明显我们要采取相反的方法。
因为我们i和j的循环方式都是1-n，所以我们使i不变，把j变一下即可。
用代码表示就是：
if(s11>mid)add(i,j+n);if(s12>mid)add(i,j);if(s21>mid)add(i+n,j+n);if(s22>mid)add(i+n,j);
（然而我还是查了题解的……我真菜）
#include#include #include #include #include #include using namespace std;typedef long long ll;inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){ if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w;}const int N=501;const int M=10000001;struct cow{ int x; int y;}e[N],s[3];struct node{ int to; int nxt;}edge[M];struct wzh{ int u; int v;}aa[1001],bb[1001];int head[N*2],dfn[N*2],low[N*2],to[N*2];int t,l,cnt;bool instack[N*4];stack q;inline void add(int u,int v){ cnt++; edge[cnt].to=v; edge[cnt].nxt=head[u]; head[u]=cnt; return;}void tarjan(int u){ t++; dfn[u]=t; low[u]=t; q.push(u); instack[u]=1; for(int i=head[u];i!=0;i=edge[i].nxt){ int v=edge[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(instack[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ int v; l++; do{ v=q.top(); q.pop(); instack[v]=0; to[v]=l; }while(v!=u); } return;}inline int dis(int a,int k1,int k2,int b){ return abs(s[k1].x-e[a].x)+abs(s[k1].y-e[a].y)+ abs(s[k1].x-s[k2].x)+abs(s[k1].y-s[k2].y)+ abs(s[k2].x-e[b].x)+abs(s[k2].y-e[b].y);}inline void clr(){ cnt=0;l=0;t=0; memset(head,0,sizeof(head)); memset(dfn,0,sizeof(dfn)); return;}int n,ans=-1;int a,b;void erfen(int l,int r){ if(l>r)return; clr(); int mid=(l+r)>>1; for(int i=1;i<=a;i++){ int u=aa[i].u;int v=aa[i].v; add(u,v+n);add(v,u+n); add(u+n,v);add(v+n,u); } for(int i=1;i<=b;i++){ int u=bb[i].u;int v=bb[i].v; add(u,v);add(v,u); add(u+n,v+n);add(v+n,u+n); } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j)continue; int s11=dis(i,1,1,j),s12=dis(i,1,2,j), s21=dis(i,2,1,j),s22=dis(i,2,2,j); if(s11>mid)add(i,j+n); if(s12>mid)add(i,j); if(s21>mid)add(i+n,j+n); if(s22>mid)add(i+n,j); } } for(int i=1;i<=n*2;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ if(to[i]==to[i+n]){ erfen(mid+1,r); return; } } ans=mid; erfen(l,mid-1); return;}//i表示与s1连，i+n表示与s2连int main(){ n=read();a=read();b=read(); s[1].x=read();s[1].y=read();s[2].x=read();s[2].y=read(); for(int i=1;i<=n;i++){ e[i].x=read(); e[i].y=read(); } for(int i=1;i<=a;i++){ aa[i].u=read(); aa[i].v=read(); } for(int i=1;i<=b;i++){ bb[i].u=read(); bb[i].v=read(); } erfen(0,6000000); printf("%d\n",ans); return 0;}