 /**//*
题意:给出n个牛棚、两个特殊点S1,S2的坐标。S1、S2直连。牛棚只能连S1或S2
还有,某些牛棚只能连在同一个S,某些牛棚不能连在同一个S
求使最长的牛棚间距离最小 距离是曼哈顿距离
使最大值最小,二分的经典应用
二分枚举最大值limit,然后重新构图,用2-SAT判定可行性
用布尔变量Xi表示第i个牛棚连到S1,~Xi表示连到S2
检查每一个约束条件,构图:
1.hate关系的i,j Xi->~Xj ~Xi->Xj Xj->~Xi ~Xj->Xi
2.friend关系的i,j Xi->Xj ~Xi->~Xj Xj->Xi ~Xj->~Xi
接下来的也要检查,因为引入参数,就是多了约束条件了
这四种情况就是i,j到达对方的所有情况了
3.dist(i,S1)+dist(S1,j)>limit Xi->~Xj Xj->Xi
4.dist(i,S2)+dist(S2,j)>limit ~Xi->Xj ~Xj->Xi
5.dist(i,S1)+dist(S1,S2)+dist(S2,j)>limit Xi->Xj ~Xj->~Xi
5.dist(i,S2)+dist(S2,S1)+dist(S1,j)>limit ~Xi->~Xj Xj->Xi

然后求SCC 判断Xi与~Xi是否在同一个SCC中,是的话就有矛盾

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

const int MAXN = 500;
const int INF = 1000000000;

int N,A,B;

struct Two
  {
int x,y;
};
Two pt[MAXN+10],s1,s2;
Two fre[MAXN*2+10],hate[MAXN*2+10];

struct Graph
  {
vector<int>G[2*MAXN+10],_G[2*MAXN+10];
int ID[MAXN*2+10],ord[MAXN*2+10];
int SCC;
void init(int n)
 {
for(int i=1;i<=n;i++)
 {
G[i].clear();
_G[i].clear();
}
}
void add(int a,int b)
 {
G[a].push_back(b);
_G[b].push_back(a);
}
void dfs1(int u)
 {
ID[u]=1;
for(int i=0,size=_G[u].size();i<size;i++)
 {
int v=_G[u][i];
if(!ID[v])dfs1(v);
}
ord[++SCC]=u;
}
void dfs2(int u)
 {
ID[u]=SCC;
for(int i=0,size=G[u].size();i<size;i++)
 {
int v=G[u][i];
if(!ID[v])dfs2(v);
}
}
void kosaraju()
 {
memset(ID,0,sizeof(ID));
SCC=0;
for(int i=1;i<=2*N;i++)
 {
if(!ID[i])dfs1(i);
}
memset(ID,0,sizeof(ID));
SCC=0;
for(int i=2*N;i;i--)
 {
if(!ID[ord[i]])
 {
SCC++;
dfs2(ord[i]);//
}
}
}

}graph;

inline int dist(Two &a,Two &b)
  {
return abs(a.x-b.x)+abs(a.y-b.y);
}
bool chk(int limit)
  {
graph.init(2*N);
//build
for(int i=1;i<N;i++)
for(int j=i+1;j<=N;j++)
 {
//dist(i,s1)+dist(j,s1)>L i0->j1 j0->i1
if(dist(pt[i],s1)+dist(pt[j],s1)>limit)
 {
graph.add(i,j+N);
graph.add(j,i+N);
}
//dist(i,s2)+dist(j,s2)>L i1->j0 j1->i0
if(dist(pt[i],s2)+dist(pt[j],s2)>limit)
 {
graph.add(i+N,j);
graph.add(j+N,i);
}
//dist(i,s1)+dist(s1,s2)+dist(s2,j)>L i0->j0 j1->i1
if(dist(pt[i],s1)+dist(s1,s2)+dist(s2,pt[j])>limit)
 {
graph.add(i,j);
graph.add(j+N,i+N);
}
//dist(i,s2)+dist(s2,s1)+dist(s1,j)>L i1->j1 j0->i0
if(dist(pt[i],s2)+dist(s2,s1)+dist(s1,pt[j])>limit)
 {
graph.add(i+N,j+N);
graph.add(j,i);
}
}
for(int i=1;i<=A;i++)
 {
//i0->j1,i1->j0,j0->i1,j1->i0
graph.add(hate[i].x,hate[i].y+N);
graph.add(hate[i].x+N,hate[i].y);
graph.add(hate[i].y,hate[i].x+N);
graph.add(hate[i].y+N,hate[i].x);
}
for(int i=1;i<=B;i++)
 {
//i0->j0,i1->j1,j0->i0,j1->i1
graph.add(fre[i].x,fre[i].y);
graph.add(fre[i].x+N,fre[i].y+N);
graph.add(fre[i].y,fre[i].x);
graph.add(fre[i].y+N,fre[i].x+N);
}
graph.kosaraju();
for(int i=1;i<=N;i++)
 {
if(graph.ID[i]==graph.ID[i+N])return false;
}
return true;
}
int main()
  {
int Max;
while(~scanf("%d%d%d",&N,&A,&B))
 {
scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);
//Max = 0;
for(int i=1;i<=N;i++)
 {
scanf("%d%d",&pt[i].x,&pt[i].y);
//Max = max(Max,dist(pt[i],s1));
//Max = max(Max,dist(pt[i],s2));
}
//Max = 2*Max+dist(s1,s2)+1;
for(int i=1;i<=A;i++)
scanf("%d%d",&hate[i].x,&hate[i].y);
for(int i=1;i<=B;i++)
scanf("%d%d",&fre[i].x,&fre[i].y);

int left = 0,right = INF;
while(right-left>1)
 {
int mid = (right+left)>>1;
if(chk(mid))right=mid;
else left=mid;
}
if(right==INF)puts("-1");
else printf("%d\n",right);
}
return 0;
}
|