# 題目: UVa 10557 – XYZZY
# 題目說明
給一張有向圖,每個點都有能量變化 (可能正可能負),起點為 100 能量
求起點是否能走到終點
INPUT:
每筆測資第一行有一個整數 n ,代表有 n 個點,若 n = -1 結束程式
接下來有 n 行,依序為 1 ~ n 個點的資訊,每行至少有兩個整數 val 、 j
val代表該點的能量消耗j代表接下來有j個整數,該點連接到這些整數
OUTPUT:
從起點 ( 1 ) 能走到終點 ( n ) 輸出 winnable ,否則輸出 hopeless
# 解題方法
因為題目為能量消耗,所以我們要找最大路徑
當有正環發生時,若該點能走到終點,則能量無限,直接輸出 winnable
透過 dfs 從終點反向找,終點是否能走到該點
先建圖,同時建一個反向的圖方便 dfs
接著以 bellman 演算法找到最大路徑,之後判斷正環
有則執行上述,無則判斷終點的能量是否大於 0 即可
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <unordered_set> | |
using namespace std; | |
vector< vector<int> > G; | |
vector< vector<int> > G_; | |
vector<int> energy; | |
vector<int> dis; | |
unordered_set<int> us; | |
void dfs(int u) | |
{ | |
us.emplace(u); | |
for (auto& v : G_[u]) if (!us.count(v)) dfs(v); | |
} | |
bool bellman(int n) | |
{ | |
dis[1] = 100; | |
for (int i = 0; i < n - 1; ++i) for (int u = 1; u <= n; ++u) | |
{ | |
for (auto& v : G[u]) if (dis[u]) dis[v] = max(dis[v], dis[u] + energy[v]); | |
} | |
for (int u = 1; u <= n; ++u) for (auto& v : G[u]) | |
{ | |
if (dis[u] && dis[v] < dis[u] + energy[v]) | |
{ | |
if (us.count(v)) return true; | |
dis[v] = dis[u] + energy[v]; | |
} | |
} | |
return dis[n]; | |
} | |
int main() | |
{ | |
// fast io | |
ios::sync_with_stdio(false); | |
cin.tie(nullptr); | |
cout.tie(nullptr); | |
int n; | |
while (cin >> n, n != -1) | |
{ | |
// init | |
G.assign(n + 1, vector<int>()); | |
G_.assign(n + 1, vector<int>()); | |
energy.assign(n + 1, 0); | |
dis.assign(n + 1, 0); | |
us.clear(); | |
for (int i = 1; i <= n; ++i) | |
{ | |
int val, j, nxt; | |
cin >> val >> j; | |
energy[i] = val; | |
while (j--) cin >> nxt, G[i].emplace_back(nxt), G_[nxt].emplace_back(i); | |
} | |
dfs(n); | |
// bellman algorithm | |
cout << (bellman(n) ? "winnable\n" : "hopeless\n"); | |
} | |
return 0; | |
} |
# 參考資料
https://www.larrysprognotes.com/UVa%20-%2010557/