Home > Database > Mysql Tutorial > HDU 1815, POJ 2749 Building roads(2

HDU 1815, POJ 2749 Building roads(2

WBOY
Release: 2016-06-07 15:44:06
Original
1266 people have browsed it

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>
Copy after login
Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template