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; }