首页 > 代码库 > POJ 2749--Building roads（2-SAT）
POJ 2749--Building roads（2-SAT）
题意：John有n个牛棚，每个牛棚都住着一些牛，这些牛喜欢串门（drop around， 学到了。。。），所以John想要建几条路把他们连接起来。他选择的方法是建两个相连中转站，然后每个牛棚连接其中一个中转站就好啦。现在的问题是有一些牛相互憎恨，所以不能连同一个中转站，而又有一些牛相互喜欢，必须连同一个中转站（再次感叹，人不如牛。。），现在要你来建边，要求，任意两个牛棚的距离的最大距离最短。两点距离是指哈密顿距离。比如u, v连的是同一个中转站s1，距离就是dis(u,s1)+dis(v,s1) 如果连不同的中转站就是dis(u,s1)+dis(v,s2)+dis(u,v)，题意真的好不清楚啊
输入就是每个牛棚的坐标的中转站的坐标，已经牛之间的憎恨和喜欢关系。
输出最小距离。不能输出-1。
题解：二分。。。然后符合要求的边建图，2-sat求解。建图时喜欢和讨厌都要建四条边，仔细读题。。。仔细建边。。。
//我真的想吐槽我以前用的输入挂啊，我特么从哪搞来的辣鸡读入。。。用一次错一次。。。。
这套题做的我心真累。。。没有特别难的。。。但是每一道都wa的想死。。。
#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <bitset>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <list>#include <map>#include <set>#define pk(x) printf("%d\n", x)using namespace std;#define PI acos(-1.0)#define EPS 1E-6#define clr(x,c) memset(x,c,sizeof(x))typedef long long ll;const int N = 50000;const int M = 2000005;inline int Scan(){ char ch = getchar(); int data = http://www.mamicode.com/0; while (ch < ‘0‘ || ch > ‘9‘) ch = getchar(); do { data = data*10 + ch-‘0‘; ch = getchar(); } while (ch >= ‘0‘ && ch <= ‘9‘); return data;}struct Edge { int from, to, next;} edge[M];int head[N];int cntE;void addedge(int u, int v) { edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++;}int dfn[N], low[N], idx;int stk[N], top;int in[N];int kind[N], cnt;void tarjan(int u){ dfn[u] = low[u] = ++idx; in[u] = true; stk[++top] = u; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (in[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++cnt; while (1) { int v = stk[top--]; kind[v] = cnt; in[v] = false; if (v == u) break; } }}void init() { cntE = 0; memset(head, -1, sizeof head); memset(dfn, 0, sizeof dfn); memset(in, false, sizeof in); idx = top = cnt = 0;}int ax[N], ay[N];int bx[N], by[N];int dis1[N], dis2[N];int n, a, b;int dis;int cal(int x1, int y1, int x2, int y2) { return abs(x1-x2) + abs(y1-y2);}bool ok(int x) { init(); for (int i = 1; i <= n; ++i) { for (int j = i+1; j <= n; ++j) { if (dis1[i] + dis1[j] > x) addedge(i, n+j), addedge(j, n+i); if (dis2[i] + dis2[j] > x) addedge(i+n, j), addedge(j+n, i); if (dis1[i] + dis2[j] + dis > x) addedge(i, j), addedge(j+n, i+n); if (dis2[i] + dis1[j] + dis > x) addedge(i+n, j+n), addedge(j, i); } } for (int i = 0; i < a; ++i) { addedge(ax[i], ay[i] + n), addedge(ay[i] + n, ax[i]); addedge(ay[i], ax[i] + n), addedge(ax[i] + n, ay[i]); } for (int i = 0; i < b; ++i) { addedge(bx[i], by[i]), addedge(by[i], bx[i]); addedge(bx[i] + n, by[i] + n), addedge(by[i] + n, bx[i] + n); } for (int i = 1; i <= 2*n; ++i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; i++) if (kind[i] == kind[i + n]) return false; return true;}int main() { int x1, y1, x2, y2; int x, y; while (~scanf("%d%d%d", &n, &a, &b)) { x1 = Scan(); y1 = Scan(); x2 = Scan(); y2 = Scan(); dis = cal(x1, y1, x2, y2); int maxn = 0; for (int i = 1; i <= n; ++i) { x = Scan(); y = Scan(); dis1[i] = cal(x, y, x1, y1); dis2[i] = cal(x, y, x2, y2); maxn = max(maxn, max(dis1[i], dis2[i])); } maxn = maxn * 2 + dis; for (int i = 0; i < a; ++i) ax[i] = Scan(), ay[i] = Scan(); for (int i = 0; i < b; ++i) bx[i] = Scan(), by[i] = Scan(); int l = 0, r = maxn; int ans = -1; while (l <= r) { int mid = (l+r) >> 1; if (ok(mid)) ans = mid, r = mid - 1; else l = mid + 1; } printf("%d\n", ans); } return 0;}
POJ 2749--Building roads（2-SAT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。