UVa 10557 XYZZY：能量迷宮 DFS + 正環檢測

問題建模

有向圖 n 點，每點有能量值（正/負）。從 1 點出發初始能量 100，走邊到達點加該點能量。能量 ≤0 失敗。問能否到達 n 點。可重複訪問點，但若某點被訪問時能量比上次高，說明存在正能量環，可無限增益，只需判斷該點是否能達終點。

算法：DFS + 剪枝 + 可達性檢查

• visited[u] 標記是否訪問過。
• energy[u] 記錄訪問時的最大能量。
• DFS(u, curEnergy)：新能量 = curEnergy + val[u]。若 ≤0 返回。若 > energy[u] 且 visited[u]，說明找到正環 → 執行輔助 DFS 檢查 u 是否能達 n（忽略能量限制）。若能達 → 成功。否則更新 energy[u] 繼續遞歸鄰居。

關鍵代碼

int val[110], vis[110], maxE[110];
vector g[110];
bool win, reachable;
void dfsReach(int u) { // 檢查可達終點
    if (u == n) { reachable = true; return; }
    vis[u] = 1;
    for (int v : g[u]) if (!vis[v]) dfsReach(v);
}
void dfs(int u, int e) {
    e += val[u];
    if (e <= 0) return;
    if (u == n) { win = true; return; }
    if (vis[u]) {
        if (e > maxE[u]) { // 正環
            memset(vis, 0, sizeof(vis));
            reachable = false;
            dfsReach(u);
            if (reachable) { win = true; return; }
        }
        return;
    }
    vis[u] = 1; maxE[u] = e;
    for (int v : g[u]) if (!win) dfs(v, e);
    vis[u] = 0; // 回溯允許其他路徑再次訪問
}

關鍵點

主 DFS 使用 vis 防止當前路徑循環，但允許不同路徑重訪（回溯清零）。正環檢測用單獨 dfsReach 忽略能量只查連通性。