POJ-2749 : Building roads

問題概要

n(<500)個の頂点がある。これらを二つあるターミナルのどちらかに接続する。このとき、いくつかのペアについては同じターミナルに接続する必要があり、またいくつかのペアは異なるターミナルに接続しなければならない。このとき、グラフの直径を最小化する問題。

解法

見るからに二分探索+2SAT風。

acceptされたコード

実際には定数倍最適化を加えた。

int getDist(int y0, int x0, int y1, int x1) {
	return abs(y0 - y1) + abs(x0 - x1);
}

Graph G;

const int MAX_N = 500;
const int MAX_A = 1000;

int N, H, L;
int SY[2], SX[2];
int ys[MAX_N], xs[MAX_N];
int distanceAB;
int dists[MAX_N][2];
int hates[MAX_A][2], likes[MAX_A][2];

bool init() {
	if (!(scanf("%d%d%d", &N, &H, &L) == 3 && N > 0)) {
		return false;
	}
	for (int k = 0; k < 2; ++k) {
		scanf("%d%d", SX+k, SY+k);
	}
	for (int i = 0; i < N; ++i) {
		scanf("%d%d", xs+i, ys+i);
	}
	for (int i = 0; i < H; ++i) {
		for (int k = 0; k < 2; ++k) {
			scanf("%d", hates[i]+k);
			--hates[i][k];
		}
	}
	for (int i = 0; i < L; ++i) {
		for (int k = 0; k < 2; ++k) {
			scanf("%d", likes[i]+k);
			--likes[i][k];
		}
	}
	return true;
}

bool check(const int test) {
	G.init(2*N);
	for (int i = 0; i < N; ++i) { // set i to A
		for (int j = i + 1; j < N; ++j) {
			for (int k = 0; k < 2; ++k) {
				if (dists[i][k] + dists[j][k] > test) {
					G.addDirectedEdge(2*i+k, 2*j+(k^1));
					G.addDirectedEdge(2*j+k, 2*i+(k^1));
				}
				if (dists[i][k] + dists[j][k^1] + distanceAB > test) {
					G.addDirectedEdge(2*i+k, 2*j+k);
					G.addDirectedEdge(2*j+(k^1), 2*i+(k^1));
				}
			}
		}
	}

	for (int i = 0; i < H; ++i) {
		for (int k = 0; k < 2; ++k) {
			G.addDirectedEdge(2*hates[i][0]+k, 2*hates[i][1]+(k^1));
			G.addDirectedEdge(2*hates[i][1]+k, 2*hates[i][0]+(k^1));
		}
	}

	for (int i = 0; i < L; ++i) {
		for (int k = 0; k < 2; ++k) {
			G.addDirectedEdge(2*likes[i][0]+k, 2*likes[i][1]+k);
			G.addDirectedEdge(2*likes[i][1]+(k^1), 2*likes[i][0]+(k^1));
		}
	}

	vector<int> components;
	calcStronglyConnectedComponent(G, components);
	for (int i = 0; i < N; ++i) {
		if (components[2*i+0] == components[2*i+1]) {
			return false;
		}
	}
	return true;
}

int solve() {
	distanceAB = getDist(SY[0], SX[0], SY[1], SX[1]);
	for (int i = 0; i < N; ++i) {
		for (int k = 0; k < 2; ++k) {
			dists[i][k] = getDist(ys[i], xs[i], SY[k], SX[k]);
		}
	}

	int low = -1, high = int(4e6);
	for (;high - low > 1;) {
		const int mid = (high + low) / 2;
		(check(mid) ? high : low) = mid;
	}
	return high == int(4e6) ? -1 : high;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}

	return 0;
}