hdu3622 2-sat问题，二分+判断有无解即可。

/*2-sat问题初破！题意：每一对炸弹只能选一个（明显2-sat），每个炸弹半径自定，爆炸范围不可

相交，求那个最小半径的最大值（每种策略的最小半径不同）。思：最优解：必然是选择的点最近

的俩个距离/2，其他半径大小无纺，不妨设他们都为该最小半径。求最小值最大，二分答案，每次判定

R是否可行，可行就往大的搜索，注意精度r-l<10^-4才可过。该题不需要输出方案，只需判定是否矛盾的

点在同一个SCC中即可。*/

#include<iostream>  //G++ 343ms，/c++，898ms 不知道为神马。。。求解释。。

#include<cstdio>

#include<cstring>

#include<vector>

#include<stack>

#include<cmath>

using namespace std;

int n;const int MAX=201;

struct points   //点，01,23,45.。。相连为一对，x^1取对应点（改变奇偶性）

{

    int x,y;

};

points  point[MAX];

int low[MAX];int dfn[MAX];int visited[MAX];bool is_instack[MAX];stack<int>s;

int times=0; int scc[MAX]; int numblock;

vector<vector<int> >edges(MAX);  //原图

void initialize()         //初始化要注意！看哪里新建图，新遍历了。因为它耽误了好久！

{

    numblock=times=0;

    for(int i=0;i<2*n;i++)

     {

         visited[i]=low[i]=dfn[i]=is_instack[i]=0;

         edges[i].clear();

         scc[i]=-1;

     }

}

void tarjan(int u)    //有向图dfs，这个不解释

{

    low[u]=dfn[u]=++times;

    is_instack[u]=1;

    s.push(u);

    int len=edges[u].size();

      for(int i=0;i<len;i++)

      {

          int v=edges[u][i];

          if(visited[v]==0)

           {

               visited[v]=1;

               tarjan(v);

               if(low[u]>low[v])low[u]=low[v];

           }

           else if(is_instack[v]&&dfn[v]<low[u])

           {

               low[u]=dfn[v];

           }

      }

     if(dfn[u]==low[u])

     {

          numblock++;

         int cur;

         do

         {

             cur=s.top();

             is_instack[cur]=0;

             s.pop();

             scc[cur]=numblock;

         }while(cur!=u);

     }

}

double dis(points a,points b)  //距离的平方，比较平方即可（据说更精准）。

{

    double temp=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);

    return (temp);

}

bool check(double r)

{

     initialize();  //哪里初始化很重要！

    for(int i=0;i<2*n;i++)     //根据r建图

      for(int j=i+1;j<2*n;j++)

      {

          if(((i>>1)!=(j>>1))&&dis(point[i],point[j])<4*r*r)   //这里的读入很妙（学来的），等价偶数枚举其大2之后的，奇数枚举其后（比他大1）所有

             {

                   edges[i].push_back(j^1);

                   edges[j].push_back(i^1);

             }

      }

     for(int i=0;i<2*n;i++)

       {

           if(visited[i]==0)

             {

                 visited[i]=1;

                 tarjan(i);

             }

       }

     for(int i=0;i<2*n;i+=2)

     {

       if(scc[i]==scc[i+1])  //矛盾的点在一个SCC中，

        {

            return false;

        }

     }

     return true;

}

void readin()

{

    for(int i=0;i<n;i++)

    {

       scanf("%d%d%d%d",&point[i*2].x,&point[i*2].y,&point[i*2+1].x,&point[i*2+1].y);

    }

}

int main()

{

    while(~scanf("%d",&n))

    {

        readin();

        double r;double left=0,right=10001,mid;

        while(right-left>0.0001)      //二分答案！

        {

            mid=(right+left)/2;

            if(check(mid))

            {

                left=mid;

            }

            else

            {

                right=mid;

            }

        }

        printf("%.2f\n",left);

    }

}

巴特西

hdu3622 2-sat问题，二分+判断有无解即可。

最新文章

热门文章