題目鏈接：http://poj.org/problem?id=1932

題意：根據給出的關系圖，判斷是否存在一條從1到n的路徑，且最終的cost值為正值,初始值為100。中間各個room的值有正有負。但在求路徑的時候，任何一點的value都不能小于或者等于零，否則這條路就不能通。當然，如果有正環，并且可以從1到n是連通的，那么就一定winnable。

解題思路：如果圖中出現正環，并且通過這個正環可以到達終點，那么肯定是winnable，所以可以用spfa算法找最大路徑，如果某點進入隊列的次數大于n，說明肯定是有正環出現，把它的dis設置為INF，這樣可以保證通過后面的點不會出現負值。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 105; const int inf = 0x3f3f3f3f; struct Edge {int to,next; }edge[maxn*maxn]; int n,tot,cnt[maxn],head[maxn],val[maxn]; int dis[maxn]; bool inq[maxn];void addedge(int u,int v) {edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; }void spfa(int src,int des) {queue<int> q;memset(inq,false,sizeof(inq));memset(cnt,0,sizeof(cnt));for(int i = 1; i <= n; i++) dis[i] = -inf;dis[src] = val[src];q.push(src);inq[src] = true;while(!q.empty()){int u = q.front();q.pop();inq[u] = false;if(cnt[u] > n) dis[u] = inf;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(dis[v] < dis[u] + val[v] && dis[u] + val[v] > 0){dis[v] = dis[u] + val[v];if(inq[v] == false && cnt[v] <= n){inq[v] = true;q.push(v);cnt[v]++;}}}}if(dis[des] > 0) printf("winnable\n");else printf("hopeless\n"); }int main() {while(scanf("%d",&n)!=EOF){if(n == -1) break;tot = 0;memset(head,-1,sizeof(head));for(int i = 1; i <= n; i++){scanf("%d",&val[i]);int k,num;scanf("%d",&num);for(int j = 1; j <= num; j++){scanf("%d",&k);addedge(i,k);}}val[1] = 100;spfa(1,n);}return 0; }

總結

以上是生活随笔為你收集整理的poj 1932(spfa判断环)的全部內容，希望文章能夠幫你解決所遇到的問題。

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