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