POJ 2749 2SAT判定+二分

时间:2023-03-08 17:45:39

题意:图上n个点,使每个点都与俩个中转点的其中一个相连(二选一,典型2-sat),并使任意两点最大

距离最小(最大最小,2分答案),有些点相互hata,不能选同一个中转点,有些点相互LOVE,必需选相同中转点

(显然是2sat条件)。

关键:每次二分枚举limit,按limit建图,需要注意的是每条逻辑语句对应两条边(相互对称,逻辑上互为假言易位),

如:必需连通一个点,逻辑语句俩条:a->b,b->a,对应各自假言易位式,4条边。

相信二sat不再是问题了。

#include<iostream>//1200ms/2000ms 1A
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
struct point
{
int x,y;
};
vector<vector<int> >e(1050);
int n,a,b;point s1,s2; int maxdis=4000001;
point po[505]; point hate[1005]; point love[1005];
int absint(int x)
{
if(x<0)return -x;
return x;
}
int dis(point aa,point bb) //距离
{
return absint(aa.x-bb.x)+absint(aa.y-bb.y);
}
void build(int limit) //每次二分后建图
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) //注意不要加ELSE
{
if(i==j)continue;
if((dis(po[i],s1)+dis(po[j],s2)+dis(s1,s2))>limit) //无法到达了,
{
e[2*i-1].push_back(2*j-1);
e[2*j-2].push_back(2*i-2);
}
if((dis(po[i],s1)+dis(po[j],s1))>limit)
{
e[2*i-1].push_back(2*j-2);
e[2*j-1].push_back(2*i-2);
}
if((dis(po[i],s2)+dis(po[j],s2))>limit)
{
e[2*i-2].push_back(2*j-1);
e[2*j-2].push_back(2*i-1);
}
}
for(int i=0;i<a;i++) //相互憎恨的
{
e[hate[i].x*2-1].push_back(hate[i].y*2-2);
e[hate[i].y*2-1].push_back(hate[i].x*2-2);
e[hate[i].x*2-2].push_back(hate[i].y*2-1);
e[hate[i].y*2-2].push_back(hate[i].x*2-1);
}
for(int i=0;i<b;i++) //相互喜爱的
{
e[love[i].x*2-1].push_back(love[i].y*2-1);
e[love[i].y*2-2].push_back(love[i].x*2-2);
e[love[i].y*2-1].push_back(love[i].x*2-1);
e[love[i].x*2-2].push_back(love[i].y*2-2);
}
}
int vis[1050];int dfn[1050];int low[1050];bool instack[1050];int block[1050];
int times=0; stack<int>s; int num=0;
void tarjan(int u) //下边是2sat缩点判断可行
{
dfn[u]=low[u]=++times;
instack[u]=1;
s.push(u);
int len=e[u].size();
for(int i=0;i<len;i++)
{
int v=e[u][i];
if(!vis[v])
{
vis[v]=1;
tarjan(v);
if(low[u]>low[v])low[u]=low[v];
}
else if(instack[v]&&dfn[v]<low[u])
low[u]=dfn[v];
}
if(dfn[u]==low[u])
{
num++;
int cur;
do{
cur=s.top();s.pop();
instack[cur]=0;
block[cur]=num;
}while(cur!=u);
}
}
bool check(int limit)
{
for(int i=0;i<=2*n-1;i++)
{
e[i].clear();
block[i]=vis[i]=dfn[i]=low[i]=instack[i]=0;
}
num=times=0;
build(limit);
for(int i=0;i<=2*n-1;i++)
if(!vis[i])
{
vis[i]=1;
tarjan(i);
}
for(int i=0;i<=2*n-1;i+=2)
if(block[i]==block[i+1])
return 0;
return 1;
}
int main()
{
scanf("%d%d%d",&n,&a,&b);scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);
for(int i=1;i<=n;i++)
scanf("%d%d",&po[i].x,&po[i].y);
for(int i=0;i<a;i++)
scanf("%d%d",&hate[i].x,&hate[i].y);
for(int i=0;i<b;i++)
scanf("%d%d",&love[i].x,&love[i].y);
int right=maxdis,left=0,mid;
if(!check(maxdis)){printf("-1\n");return 0;}
while(right>left+1)
{
mid=(right+left)/2;
if(check(mid))
{
right=mid;
}
else
left=mid;
}
if(check(right-1))printf("%d\n",right-1);
else printf("%d\n",right);
return 0;
}