HDU 1815， POJ 2749 Building roads（2

WBOY

リリース： 2016-06-07 15:44:06

オリジナル

1221 人が閲覧しました

HDU 1815， POJ 2749 Building roads 题目链接HDU 题目链接POJ 题意: 有n个牛棚，还有两个中转站S1和S2， S1和S2用一条路连接起来。为了使得任意牛棚两个都可以有道路联通，现在要让每个牛棚都连接一条路到S1或者S2。有a对牛棚互相有仇恨，所以不能让他们

HDU 1815， POJ 2749 Building roads

题目链接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>

ログイン後にコピー