POJ-2749-Building roads(2-sat)-白红宇

POJ-2749-Building roads(2-sat)

阅读量：5144 次

发布时间：2019-06-13

本文共 1702 字，大约阅读时间需要 5 分钟。

POJ 2-sat六题最后一题

http://blog.sina.com.cn/s/blog_64675f540100k2xf.html

poj 六道2-sat最后一题第六题：

题目描述：有n个农场，每个农场有坐标x，y。

有两个集合点s1和s2（也有坐标），每个农场必须连接其中的一个（有且仅有一个）。

然后有A个条件，每个条件a，b表示a农场不能和b农场连接在一个集合点。

然后再有B个条件，每个条件a，b表示a农场必须和b农场连接在一个集合点。

问你，在各种合法的连接情况中，任何两个农场间的距离的最大值的最小值是多少。

解题报告：

每个农场i分成两个点，i和i + n，前面表示连接左侧集合点，后面的表示连接右侧集合点。

对于条件A中的ab，连接

<a, b + n> <a + n, b> <b, a + n> <b + n, a>

这样就保证了ab不再一个集合点。同理，B条件也很好写。

然后就是用二分枚举答案（距离的最大值）。

对于每一次枚举的答案key，枚举任意两个农场a,b, 如果他俩的4种距离（a->s1->s1>b, a->s2->s2->b, a->s1->s2->b, a->s2->s1->b)有大于key的，就加入判定条件，不能这样连接。

// File Name: 2749.cpp// Author: zlbing// Created Time: 2013/2/5 21:18:58#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include 
               
                using namespace std;#define MAXN 1000struct TwoSAT{ int n; vector
                
                 G[MAXN*2]; bool mark[MAXN*2]; stack
                 
                  S; bool dfs(int x) { if(mark[x^1])return false; if(mark[x])return true; mark[x]=true; S.push(x); for(int i=0;i
                  
                   M) { solver.add_clause(i*2,j*2+1); solver.add_clause(j*2,i*2+1); } if(count(i,1)+count(j,1)>M) { solver.add_clause(i*2+1,j*2); solver.add_clause(j*2+1,i*2); } if(count(i,1)+count(j,0)+AlenB>M) { solver.add_clause(i*2+1,j*2+1); solver.add_clause(j*2,i*2); } if(count(i,0)+count(j,1)+AlenB>M) { solver.add_clause(i*2,j*2); solver.add_clause(j*2+1,i*2+1); } } if(solver.solve())return true; else return false;}#define MAXN 4000000int main(){ while(~scanf("%d%d%d",&N,&A,&B)) { scanf("%d%d%d%d",&s[0][0],&s[0][1],&s[1][0],&s[1][1]); AlenB=abs(s[0][0]-s[1][0])+abs(s[0][1]-s[1][1]); for(int i=0;i