POJ 2749 2SAT判定+二分

题意：图上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;

}

巴特西

POJ 2749 2SAT判定+二分

最新文章

热门文章