HDU 1815， POJ 2749 Building roads
题意:
有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 < 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;}
版权声明：本文博主原创文章。博客，未经同意不得转载。