鏈接：

http://acm.hdu.edu.cn/showproblem.php?pid=1317

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=29015#problem/F

XYZZY

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1701????Accepted Submission(s): 419


Problem Description It has recently been discovered how to run open-source software on the Y-Crate gaming device. A number of enterprising designers have developed Advent-style games for deployment on the Y-Crate. Your job is to test a number of these designs to see which are winnable.?
Each game consists of a set of up to 100 rooms. One of the rooms is the start and one of the rooms is the finish. Each room has an energy value between -100 and +100. One-way doorways interconnect pairs of rooms.?

The player begins in the start room with 100 energy points. She may pass through any doorway that connects the room she is in to another room, thus entering the other room. The energy value of this room is added to the player's energy. This process continues until she wins by entering the finish room or dies by running out of energy (or quits in frustration). During her adventure the player may enter the same room several times, receiving its energy each time.?

Input The input consists of several test cases. Each test case begins with n, the number of rooms. The rooms are numbered from 1 (the start room) to n (the finish room). Input for the n rooms follows. The input for each room consists of one or more lines containing:?

the energy value for room i?
the number of doorways leaving room i?
a list of the rooms that are reachable by the doorways leaving room i?
The start and finish rooms will always have enery level 0. A line containing -1 follows the last test case.?

Output In one line for each case, output "winnable" if it is possible for the player to win, otherwise output "hopeless".?

Sample Input 5 0 1 2 -60 1 3 -60 1 4 20 1 5 0 0 5 0 1 2 20 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 21 1 3 -60 1 4 -60 1 5 0 0 5 0 1 2 20 2 1 3 -60 1 4 -60 1 5 0 0 -1
Sample Output hopeless hopeless winnable winnable
Source University of Waterloo Local Contest 2003.09.27
Recommend Eddy

題意:

? ? 有 N 個房間, 編號從 1 到 N 。
? ? 每次進入一個房間, 能量值可能增加也可能減少
? ? 問：從第一個房間開始走, 給你 100 個能量值。
? ? ? ? 問你是否能走到第 N 個房間。


? ? 第一行 N ?輸入房間的個數
? ? 然后下面 N 行數據：
? ? ? ? 第 i ?行數據的第一個表示進入該房間得到的能量【可正可負】
? ? ? ? 第二個表示從該房間出發能到達的房間個數 num
? ? ? ? 剩下 num 個數表示可以到達的房間編號

算法：Bellman_ford() 判斷正環

注意：是有向圖,
? ? ? 然后建圖的時候要注意下, 邊是沒有權的。。。
? ? ? 點有權。

思路：

? ? ? 其實開始沒看題目的時候，沒有看到群里的吐槽也不會想到用 Bellman_ford()
? ? ? 如果圖中存在正環, 那么就可以不停的走這個環來增加能量,
? ? ? 如果環中的點能到達 N 那么肯定是贏了。。。
? ? ? 但是由于這個先入為主的思想,開始很容易的就讓我忽略了,這題的本質是到達 N 的時候還有能量。
? ? ? 然后就是各種不注意,各種 WA 的血淚史。。。。然后網上各種高深的題解。 ? ? ? 直到看到了一篇用 Bellman_ford 寫的


? ? ? 加邊建圖的過程同時記錄連通性, 先判斷 1 與 N 在不考慮能量的時候是否連通【不判斷也可以，只是個無關緊要的優化】 ? ? ? 然后就是套用 Bellman_ford() 判斷是否有正環


? ? ? 注意：當不存在正環的時候, 不要像以前用這個算法時直接跳出
? ? ? ? ? ? 因為我們的主要目的不是判斷正環，而是要使得到達 N 還有能量。


? ? ? 那么贏的可能性就兩種了：
? ? ? 1.沒有正環, 但是通過Bellman_ford() 的松弛操作, 到 N 的能量值 > 0
? ? ? 2.存在正環, 正環中的點, 能到達終點。

code：

#include<stdio.h> #include<string.h> #include<iostream> using namespace std;const int maxn = 110; const int INF = 10000000000;int w[maxn][maxn]; // 判斷圖的連通性 int en[maxn]; //進入該點的能量值 int d[maxn]; //每一點的能量值 int n,m; //n 個點, m 條邊struct Edge{int u,v; }edge[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++)w[i][j] = w[i][j] || (w[i][k] && w[k][j]); //不要寫錯了 WA 的都是淚。。。 }bool Bellman_ford() {for(int i = 1; i <= n; i++) d[i] = -INF;d[1] = 100; // 初始第一個點有 100 個能量for(int i = 1; i < n; i++){for(int j = 0; j < m; j++){int u = edge[j].u;int v = edge[j].v;if(d[v] < d[u]+en[v] && d[u]+en[v] > 0) //松弛d[v] = d[u]+en[v]; //是加上點的權。。。} //注意：不能像以前一樣不能松弛了,就直接返回 false 因為判斷正環的目的是使 d[n] > 0}for(int i = 0; i < m; i++){int u = edge[i].u;int v = edge[i].v;if(d[v] < d[u]+en[v] && d[u]+en[v] > 0) //如果存在正環if(w[v][n]) //正環中的點能夠到達終點return true;}return d[n]>0; // 不存在正環, 判斷能否依靠 100 個能量值到達終點 }int main() {while(scanf("%d", &n) != EOF){if(n == -1) break;m = 0; // 初始化邊memset(w, 0, sizeof(w));memset(en, 0, sizeof(en));for(int i = 1; i <= n; i++) w[i][i] = 1;int num;for(int i = 1; i <= n; i++){int v;scanf("%d%d", &en[i], &num);while(num--) //注意是單向的{scanf("%d", &v);edge[m].u = i;edge[m++].v = v;w[i][v] = 1; // 有向圖, 不要傻逼的加上 w[v][i] = 1}}floyd(); // 考查有向圖的連通性/*if(!w[1][n]){printf("hopeless\n"); continue;}*/if(Bellman_ford()) printf("winnable\n");else printf("hopeless\n");}return 0; }

?

轉載于:https://www.cnblogs.com/pangblog/p/3255870.html

總結

以上是生活随笔為你收集整理的hdu 1317 XYZZY【Bellheman_ford 判断正环小应用】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。