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

【题目链接】

poj： 

hdu： 

【题目大意】

有n个牛棚， 还有两个中转站S1和S2， S1和S2用一条路连接起来。 为了使得任意牛棚两个都可以有道路联通，现在要让每个牛棚都连接一条路到S1或者S2。

有a对牛棚互相有仇恨，所以不能让他们的路连接到同一个中转站。还有b对牛棚互相喜欢，所以他们的路必须连到同一个中专站。

道路的长度是两点的曼哈顿距离。

问最小的任意两牛棚间的距离中的最大值是多少？

【思路】

两天前看了这题，当时没什么想法，今天又翻看了一下，想出来了。

每个牛棚有可以选择S1或者S2，并且有矛盾对，是2-SAT无疑。

首先这题要二分所求的距离是一定要的， 最大的问题是怎样建图？

我们枚举了任意牛棚之间的最大距离，说明如果有两个牛棚，他们选择的连接方式使得他们的距离大于最大距离，他们肯定就不能选择这种连接的，这是个矛盾对，根据这个可以加边了。

然后就是互相仇恨的和互相喜欢的建边，这个很容易想到。

写完后在poj提交，发现WA了，但是很肯定自己的算法没问题，就想到可能是二分的右边界太小了，于是改大成了400W，然后AC了。

于是又交到hdu去，结果竟然TLE了。。。搞了很久，发现还是右边界开小了，于是不断加大，最后到800W才AC了。右边界小了会TLE，这个让我想不通了，求指教

另外，每一点到S1和S2的距离预先算好，而不是每次建图时都算，这样可以省很多很多的时间

【代码】

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;const int MAXN = 1005;const int VN   = MAXN*2;const int EN   = 1200000;int n, hateNum, likeNum;int d[VN], sLen;struct Node{    int x, y;}barn[MAXN], hate[VN], like[VN], s1, s2;struct Edge{    int v, next;};struct Graph{    int size, head[VN];    Edge E[EN];    void init(){        size=0;         memset(head, -1, sizeof(head));     }    void addEdge(int u, int v){        E[size].v = v;        E[size].next = head[u];        head[u] = size++;    }}g;class Two_Sat{public:    bool check(const Graph& g, const int n){        scc(g, 2*n);        for(int i=0; i
        
          maxLen){ g.addEdge(i, j+n); g.addEdge(j, i+n); } if(l1 + r2 + sLen > maxLen){ g.addEdge(i, j); g.addEdge(j+n, i+n); } if(l2 + r1 + sLen > maxLen){ g.addEdge(i+n, j+n); g.addEdge(j, i); } if(l2 + r2 > maxLen){ g.addEdge(i+n, j); g.addEdge(j+n, i); } } for(int i=0; i
         
          >1; buildGraph(mid); if(sat.check(g, n)){ ans = mid; r = mid-1; } else l = mid+1; } printf("%d\n", ans); } return 0;}
         
        
       
      
     
    
   

转载地址：http://xpzni.baihongyu.com/