首页 > 代码库 > HDU 1815, POJ 2749 Building roads(2-sat)
HDU 1815, POJ 2749 Building roads(2-sat)
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 < n; i += 2) { g[i].clear(); g[i^1].clear(); } memset(mark, false, sizeof(mark)); } void add_Edge(int u, int uval, int v, int vval) { u = u * 2 + uval; v = v * 2 + vval; g[u^1].push_back(v); g[v^1].push_back(u); } void delete_Edge(int u, int uval, int v, int vval) { u = u * 2 + uval; v = v * 2 + vval; g[u^1].pop_back(); g[v^1].pop_back(); } bool dfs(int u) { if (mark[u^1]) return false; if (mark[u]) return true; mark[u] = true; S[sn++] = u; for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if (!dfs(v)) return false; } return true; } bool solve() { for (int i = 0; i < n; i += 2) { if (!mark[i] && !mark[i + 1]) { sn = 0; if (!dfs(i)){ for (int j = 0; j < sn; j++) mark[S[j]] = false; sn = 0; if (!dfs(i + 1)) return false; } } } return true; } } gao; const int N = 505; int n, a, b; struct Point { int x, y; void read() { scanf("%d%d", &x, &y); } } s1, s2, p[N], A[N * 2], B[N * 2]; int dis(Point a, Point b) { int dx = a.x - b.x; int dy = a.y - b.y; return abs(dx) + abs(dy); } int g[N][N][4]; bool judge(int d) { gao.init(n); for (int i = 0; i < a; i++) { gao.add_Edge(A[i].x - 1, 0, A[i].y - 1, 0); gao.add_Edge(A[i].x - 1, 1, A[i].y - 1, 1); } for (int i = 0; i < b; i++) { gao.add_Edge(B[i].x - 1, 0, B[i].x - 1, 1); gao.add_Edge(B[i].x - 1, 0, B[i].y - 1, 1); gao.add_Edge(B[i].y - 1, 0, B[i].x -1 , 1); gao.add_Edge(B[i].y - 1, 0, B[i].y - 1, 1); } for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (g[i][j][3] > 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 < n; i++) { p[i].read(); for (int j = 0; j < i; j++) { g[i][j][0] = dis(p[i], s1) + dis(p[j], s1); g[i][j][1] = dis(p[i], s2) + dis(p[j], s2); g[i][j][2] = dis(p[i], s1) + dis(p[j], s2) + dis(s1, s2); g[i][j][3] = dis(p[i], s2) + dis(p[j], s1) + dis(s1, s2); } } for (int i = 0; i < a; i++) A[i].read(); for (int i = 0; i < b; i++) B[i].read(); int l = 0, r = 7777777; if (!judge(r)) printf("-1\n"); else { while (l < r) { int mid = (l + r) / 2; if (judge(mid)) r = mid; else l = mid + 1; } printf("%d\n", l); } } return 0; }
HDU 1815, POJ 2749 Building roads(2-sat)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。