UVA 718 Skyscraper Floors - 擴展歐幾里得與圖論

問題建模

F 層樓，E 條電梯。電梯 i 到達樓層集合 { y_i + k × x_i | k ≥ 0, y_i + k×x_i ≤ F }。問從樓層 A 能否到達樓層 B（可任意換乘）。

核心子問題：兩電梯能否換乘

電梯 i, j 能換乘 ⇔ 存在非負整數 k₁, k₂ 使得：
y_i + k₁x_i = y_j + k₂x_j ≤ F

移項得線性不定方程：
x_i·k₁ - x_j·k₂ = y_j - y_i

擴展歐幾里得求解

1. 設 a = x_i, b = -x_j, c = y_j - y_i
2. 求 gcd(a, b) = d，若 c % d ≠ 0 無解
3. 得到一組特解 (x₀, y₀)
4. 通解：k₁ = x₀ + (b/d)t, k₂ = y₀ - (a/d)t
5. 施加約束：k₁ ≥ 0, k₂ ≥ 0, y_i + k₁x_i ≤ F, y_j + k₂x_j ≤ F
6. 解出 t 的上下界，若下界 ≤ 上界則有解，建立邊

圖構建與搜索

• 節點 0：起點 A，節點 E+1：終點 B，節點 1~E：電梯
• A 能直達電梯 i ⇔ (A - y_i) % x_i == 0 且 A ≥ y_i，連邊 0→i
• 同理 B 連邊 i→E+1
• 電梯間可換乘雙向連邊
• DFS/BFS 判斷 0 能否達 E+1

關鍵代碼片段

int exgcd(int a, int b, int &x, int &y) {
    if (!b) { x = 1; y = 0; return a; }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

void build2(int i, int j) { // 判斷電梯 i, j 能否換乘
    int xx, yy;
    int a = x[i], b = -x[j], c = y[j] - y[i];
    int d = exgcd(a, b, xx, yy);
    if (c % d) return;
    // 計算 t 的範圍...
    if (down > up) return;
    g[i].push_back(j); g[j].push_back(i);
}

難點與避坑

1. 通解範圍推導：需分正負情況處理不等式方向，代碼中用 ceil/floor 處理浮點邊界
2. 數據類型：中間計算可能超 int，建議用 long long
3. 多測試用例清理：每輪需重置圖、訪問數組

總結

本題融合了數論（線性不定方程整數解）、圖論（連通性判斷）與仔細的邊界處理。關鍵洞見是將換乘條件轉化為不定方程，利用通解參數 t 的範圍判斷可行性，而非暴力枚舉樓層。