HDU 4889 Scary Path Finding Algorithm：構造圖觸發變量增長

HDU 4889 Scary Path Finding Algorithm：構造圖觸發變量增長

給定一段偽代碼，要求構造一張圖，使執行該代碼後變量 doge 超過給定閾值 C。代碼邏輯：從節點 1 開始，按某規則遍歷邊，累加邊權到 doge。

核心洞察

題目給出的代碼實際上是在圖上執行類似 DFS/BFS 的遍歷，並累加邊權。構造圖的關鍵是設計邊權與拓撲，使累加和呈指數增長。

構造方法

建立 99 個節點，分兩層：1~30 和 31~60（或類似）。邊設計使得遍歷路徑經過的邊權為 2 的冪次，總和為 2³⁰ - 1 ≈ 10⁹，足夠超過 C (≤ 10⁹)。

參考構造（AC 代碼）

int f[33] = {-1};
for (int i=1; i<=30; i++) f[i] = f[i-1] * 2; // f[i] = 2^(i-1) * (-1)? 實際為 2^i 規律

while (scanf("%d", &C) != EOF) {
    puts("99 87"); // 99節點，87條邊
    for (int i=1; i<30; i++) {
        printf("%d %d 0\n", i, i+30);        // 跨層邊權 0
        printf("%d %d %d\n", i, i+1, f[29-i]); // 同層遞增邊權
        printf("%d %d %d\n", i+30, i+31, f[30-i]); // 下層遞增邊權
    }
}

原理分析

• 代碼遍歷邏輯會強制走完這兩條鏈，累加所有邊權。
• 邊權設計為 2 的冪次，總和 = Σ 2ⁱ = 2³⁰ - 1 > 10⁹。
• 節點數 99、邊數 87 為題目隱含要求（輸出格式固定）。

解題技巧

1. 仔細閱讀給定偽代碼，模擬其執行流程。
2. 構造題核心：將代碼邏輯「逆向工程」為圖結構需求。
3. 指數增長是突破大閾值的常用手法（2 的冪次、斐波納契等）。

複雜度

輸出固定大小圖，O(1)。

此題是「輸出構造」類問題的典型代表，考察對給定算法行為的深度理解與逆向構造能力。