HDU 1815， POJ 2749 Building roads 题目链接HDU 题目链接POJ 题意: 有n个牛棚， 还有两个中转站S1和S2， S1和S2用一条路连接起来。 为了使得任意牛棚两个都可以有道路联通，现在要让每个牛棚都连接一条路到S1或者S2。 有a对牛棚互相有仇恨，所以不能让他们
题目链接HDU
题目链接POJ
题意:
有n个牛棚， 还有两个中转站S1和S2， S1和S2用一条路连接起来。 为了使得任意牛棚两个都可以有道路联通，现在要让每个牛棚都连接一条路到S1或者S2。
有a对牛棚互相有仇恨，所以不能让他们的路连接到同一个中转站。还有b对牛棚互相喜欢，所以他们的路必须连到同一个中专站。
道路的长度是两点的曼哈顿距离。
问最小的任意两牛棚间的距离中的最大值是多少？
思路：二分距离，考虑每两个牛棚之间4种连边方式，然后根据二分的长度建立表达式，然后跑2-sat判断即可
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXNODE = 505;
struct TwoSet {
int n;
vector<int> g[MAXNODE * 2];
bool mark[MAXNODE * 2];
int S[MAXNODE * 2], sn;
void init(int tot) {
n = tot * 2;
for (int i = 0; i d)
gao.add_Edge(i, 0, j, 1);
if (g[i][j][2] > d)
gao.add_Edge(i, 1, j, 0);
if (g[i][j][1] > d)
gao.add_Edge(i, 0, j, 0);
if (g[i][j][0] > d)
gao.add_Edge(i, 1, j, 1);
}
}
return gao.solve();
}
int main() {
while (~scanf("%d%d%d", &n, &a, &b)) {
s1.read(); s2.read();
for (int i = 0; i <br>
<br>
</int></cmath></algorithm></vector></cstdlib></cstring></cstdio>
