# 題目: 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/