/**//* 题意:给出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; }
|