 /**//*
題意:給出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;
}
|