企业网站建设分析/seo的概念

传送门

• 题意

有N个农场，其中A对相互讨厌，不能碰面；B对相互喜欢，必须碰面。给定两个中转站S1和S2、各个农场的坐标，让每个农场连接到其中一个中转站。求最小化任意两个农场通过中转站的最大距离，若无法实现，输出-1。

• 题解：2-SAT

分析：
1.对于最小值可二分
2.根据2-SAT思想，需将题意转化为n个bool变量，考虑这种转化：考虑一个点的true为连接s1,false为连接s2。那么hate与be friends with的关系可以轻松转化，下面处理距离的关系距离的关系:

for(int x=1;x<=n;x++)for(int y=x+1;y<=n;y++){if(dist1(x)+dist1(y)>lim)add(Is(x),Isnot(y)),add(Is(y),Isnot(x));if(dist2(x)+dist2(y)>lim)add(Isnot(x),Is(y)),add(Isnot(y),Is(x));if(dist1(x)+dist2(y)+dis>lim)add(Is(x),Is(y)),add(Isnot(y),Isnot(x));if(dist2(x)+dist1(y)+dis>lim)add(Isnot(x),Isnot(y)),add(Is(y),Is(x));}

(至于原因是显而易见的)

• Code：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=1e3+50;
const int Maxm=2e6+50;
const int INF=7e6+50;typedef pair<int,int> pii;
inline int read()
{char ch=getchar();int i=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}return i*f;
}inline int Abs(int x){if(x>0)return x;return -x;}
int n,A,B,xx[Maxn],yy[Maxn],s1x,s1y,dis,s2x,s2y,tg,ans;
int low[Maxn],dfn[Maxn],st[Maxn],ins[Maxn],top,Ind,bl[Maxn],Bcnt;
int before[Maxm],to[Maxm],last[Maxn],ecnt;
pii as[Maxn],bs[Maxn];inline void add(int x,int y)
{++ecnt;before[ecnt]=last[x];last[x]=ecnt;to[ecnt]=y;
}inline int Is(int x)
{return 2*x+1;
}inline int Isnot(int x)
{return 2*x;
}inline int dist1(int x)
{return Abs(xx[x]-s1x)+Abs(yy[x]-s1y);
}inline int dist2(int x)
{return Abs(xx[x]-s2x)+Abs(yy[x]-s2y);
}inline void dfs(int now)
{low[now]=dfn[now]=++Ind;ins[st[++top]=now]=1;for(int e=last[now];e;e=before[e]){int v=to[e];if(!dfn[v]){dfs(v);low[now]=min(low[now],low[v]);}else if(ins[v]){low[now]=min(low[now],dfn[v]);}}if(low[now]==dfn[now]){Bcnt++;do{bl[st[top]]=Bcnt;ins[st[top--]]=0;}while(st[top+1]!=now);}
}inline bool check(int lim)
{ecnt=1;Ind=0;memset(last,0,sizeof(last));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));for(int i=1;i<=A;i++){int x=as[i].first,y=as[i].second;add(Is(x),Isnot(y));add(Isnot(x),Is(y));add(Is(y),Isnot(x));add(Isnot(y),Is(x));}for(int i=1;i<=B;i++){int x=bs[i].first,y=bs[i].second;add(Is(x),Is(y));add(Isnot(x),Isnot(y));add(Is(y),Is(x));add(Isnot(y),Isnot(x)); }for(int x=1;x<=n;x++)for(int y=x+1;y<=n;y++){if(dist1(x)+dist1(y)>lim)add(Is(x),Isnot(y)),add(Is(y),Isnot(x));if(dist2(x)+dist2(y)>lim)add(Isnot(x),Is(y)),add(Isnot(y),Is(x));if(dist1(x)+dist2(y)+dis>lim)add(Is(x),Is(y)),add(Isnot(y),Isnot(x));if(dist2(x)+dist1(y)+dis>lim)add(Isnot(x),Isnot(y)),add(Is(y),Is(x));}for(int i=2*n+1;i>=2;i--)if(!dfn[i])dfs(i);for(int i=1;i<=n;i++)if(bl[i*2]==bl[i*2+1])return false;return true;
}int main()
{n=read();A=read();B=read();s1x=read();s1y=read();s2x=read();s2y=read();dis=Abs(s1x-s2x)+Abs(s1y-s2y);for(int i=1;i<=n;i++){xx[i]=read();yy[i]=read();}for(int i=1;i<=A;i++)as[i].first=read(),as[i].second=read();for(int i=1;i<=B;i++)bs[i].first=read(),bs[i].second=read();int l=0,r=INF;while(l<=r){int mid=(l+r)>>1;if(check(mid))tg=1,ans=mid,r=mid-1;else l=mid+1;}if(tg)cout<<ans<<endl;else cout<<"-1";
}