Building Roads：農場建路最小化最大曼哈頓距離

題目：給定 N 個牛棚座標、兩個轉運點 S1, S2，每個牛棚必須連接 S1 或 S2（二選一），且有「互相討厭」與「必須同組」限制。目標：最小化任意兩牛棚間的最大曼哈頓距離。

核心模型

• 決策變數：每個牛棚分配給 S1 或 S2（0/1 變數）。
• 限制條件：
  • 討厭對 → 不能同組（XOR）。
  • 朋友對 → 必須同組（XNOR）。
• 目標函數：最小化 max_{i,j} dist(i,j)，其中距離為曼哈頓距離經由轉運點。

解題策略

1. 二分答案 D：檢查是否存在分配方案使所有牛棚對距離 ≤ D。
2. 檢查可行性轉化為 2-SAT 問題：
   • 每個牛棚建立布林變數 x_i（True=連 S1, False=連 S2）。
   • 距離限制轉化為子句：若 i,j 同組距離 > D → 加入 (¬x_i ∨ ¬x_j) 等。
   • 朋友/討厭限制直接對應子句。
3. 用 Tarjan SCC 判斷 2-SAT 可滿足性。

參考實作

• 陳振宇博客詳細解析
• 備用講解

此題綜合幾何、二分、2-SAT，是經典綜合難題。