思路：首先將hate和friend建邊求其次2-SAT問題，判斷是否能有解，沒解就輸出-1，否則用二分枚舉最大的長度，將兩個barn的距離小于mid的看做是矛盾，然后建邊，求2-SAT問題。找出最優解。

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<vector> #define Maxn 3010 #define Maxm 1000000 using namespace std; int dfn[Maxn],low[Maxn],vi[Maxn],head[Maxn],e,n,m,lab,top,Stack[Maxn],num,id[Maxn],A,B,ss; struct Edge{int u,v,next,l; }edge[Maxm]; struct Point{int x,y; }p[Maxn],s1,s2; struct Match{int a,b; }hate[Maxn],Friend[Maxn]; void init() {int i,j;memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(head,-1,sizeof(head));memset(id,0,sizeof(id));memset(vi,0,sizeof(vi));e=lab=num=top=0; } void add(int u,int v) {edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++; } int Dis(Point a,Point b) {return abs(a.x-b.x)+abs(a.y-b.y); } void Tarjan(int u) {int i,j,v;dfn[u]=low[u]=++lab;Stack[top++]=u;vi[u]=1;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;if(!dfn[v]){Tarjan(v);low[u]=min(low[u],low[v]);}if(vi[v])low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){++num;do{i=Stack[--top];vi[i]=0;id[i]=num;}while(i!=u);} } void build(int mid) {int i,j;init();for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(j==i)continue;if(Dis(p[i],s1)+Dis(p[j],s1)>mid){add(i,j+n);add(j,i+n);}if(Dis(p[i],s2)+Dis(p[j],s2)>mid){add(i+n,j);add(j+n,i);}if(Dis(p[i],s1)+Dis(p[j],s2)+ss>mid){add(i,j);add(j+n,i+n);}if(Dis(p[i],s2)+Dis(p[j],s1)+ss>mid){add(j,i);add(i+n,j+n);}}for(i=1;i<=A;i++){add(hate[i].a,hate[i].b+n);add(hate[i].b,hate[i].a+n);add(hate[i].a+n,hate[i].b);add(hate[i].b+n,hate[i].a);}for(i=1;i<=B;i++){add(Friend[i].a,Friend[i].b);add(Friend[i].a+n,Friend[i].b+n);add(Friend[i].b,Friend[i].a);add(Friend[i].b+n,Friend[i].a+n);} } int cal() {int i;for(i=1;i<=n*2;i++){if(!dfn[i])Tarjan(i);}for(i=1;i<=n;i++){if(id[i]==id[i+n])return 0;}return 1; } int solve() {int i,j;for(i=1;i<=A;i++){add(hate[i].a,hate[i].b+n);add(hate[i].b,hate[i].a+n);add(hate[i].a+n,hate[i].b);add(hate[i].b+n,hate[i].a);}for(i=1;i<=B;i++){add(Friend[i].a,Friend[i].b);add(Friend[i].a+n,Friend[i].b+n);add(Friend[i].b,Friend[i].a);add(Friend[i].b+n,Friend[i].a+n);}if(!cal())return -1;int l,r,mid;l=0;r=4000010;while(l+1<r){mid=(l+r)>>1;build(mid);if(cal())r=mid;elsel=mid;}return r; } int main() {int i,j,a,b,c;while(scanf("%d%d%d",&n,&A,&B)!=EOF){init();scanf("%d%d%d%d",&s1.x,&s1.y,&s2.x,&s2.y);for(i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);for(i=1;i<=A;i++)scanf("%d%d",&hate[i].a,&hate[i].b);for(i=1;i<=B;i++)scanf("%d%d",&Friend[i].a,&Friend[i].b);ss=Dis(s1,s2);printf("%d\n",solve());}return 0; }

?

轉載于:https://www.cnblogs.com/wangfang20/p/3220262.html

總結

以上是生活随笔為你收集整理的poj 2749 2-SAT问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。