欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  数据库

HDU 1815, POJ 2749 Building roads(2

程序员文章站 2024-01-30 09:02:52
...

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 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXNODE = 505;

struct TwoSet {
	int n;
	vector 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