題意：給你n個房間 開始有能量值100 判斷能否從1到第n個房間
每到一個房間可以獲得能量x(可能小於0) 每到一個房間總能量必須大於0 每個房間可以重復到達
思路：求一個從1到n的最長路 不過可能有正環 沒有正環 直接求最長路 如果有正環 判斷環中的點是否可以到達n
具體用Bellman-Ford算法 雖然復雜度是(n*m)這題應該可以了 如果迭代n-1次之後還能松弛 說明有正環 然後用floyd判斷是否可達
#include#include #include #include using namespace std; const int maxn = 110; struct edge { int u, v, w; }; vector G; int dis[maxn]; bool vis[maxn]; int n, m; int a[maxn][maxn]; void floyd() { for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) a[i][j] = a[i][j] || (a[i][k] && a[k][j]); } bool Bellman_Ford() { for(int i = 1; i <= n; i++) dis[i] = -999999999; dis[1] = 100; for(int i = 1; i < n; i++) { for(int j = 0; j < G.size(); j++) { edge e = G[j]; if(dis[e.v] < dis[e.u] + e.w && dis[e.u] + e.w > 0) dis[e.v] = dis[e.u] + e.w; } } //printf("%d\n", dis[n]); if(dis[n] > 0) return true; for(int i = 0; i < G.size(); i++) { edge e = G[i]; if(dis[e.v] < dis[e.u] + e.w && dis[e.u] + e.w > 0) { //puts("sss"); dis[e.v] = dis[e.u] + e.w; if(a[e.v][n]) return true; } } return false; } int main() { while(scanf("%d", &n) && n != -1) { //for(int i = 0; i <= n; i++) G.clear(); memset(a, 0, sizeof(a)); for(int i = 1; i <= n; i++) { int t, v, w; scanf("%d %d", &w, &t); while(t--) { scanf("%d", &v); G.push_back((edge){i, v, w}); //G.push_back((edge){v, i, w}); a[i][v] = 1; //a[v][i] = 1; //G[v].push_back((edge){u, w}); } } floyd(); if(Bellman_Ford()) puts("winnable"); else puts("hopeless"); } return 0; }
