首页 > 代码库 > hdu1317 XYZZY Floyd + Bellman_Ford
hdu1317 XYZZY Floyd + Bellman_Ford
这题，我在学搜索的时候做过。不过好像不叫这名字。
1、先用Floyd算法判断图的连通性。如果1与n是不连通的，输出hopeless。
2、用Bellman_Ford算法判断是否有正圈，如果某点有正圈，并且该点与第n点是连通的。就输出winnable。当然，没有正圈的情况下，可以到达也是可以的。然后就是如何找正圈的问题。Bellman_Ford算法可以判断有没有负圈。Bellman_Ford是解决最短路问题的，核心是松弛法。如果dist[v]<dist[u]+Map[u][v],则dist[v]=dist[u]+Map[u][v]。在循环n-1次以后，如果还存在dist[v]<dist[u]+Map[u][v]，则说明有负圈。这样，我们找正圈也有方法了：dist数组初始化为负无穷。如果dist[v]>dist[u]+Map[u][v],则dist[v]=dist[u]+Map[u][v]。循环n-1次以后，如果还存在dist[v]>dist[u]+Map[u][v]，则说明有正圈。
其中，要注意的是。可以往下一房间走的条件是当前的能量值大于0。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 105, M = N*N/2, INF=0x3f3f3f3f;int dist[N],f[N][N], g[N];struct node{ int x,y;}e[M];int n,m;void floyd(){ int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) f[i][j]=f[i][j]||(f[k][j]&&f[i][k]);}bool bellman_ford(int s){ int i,j,k; for(i=1;i<=n;i++) dist[i]= -INF; dist[s]=100; for(i=1;i<n;i++) //n-1次 { for(j=0;j<m;j++) { int x=e[j].x, y=e[j].y; if(dist[y]<dist[x] + g[y]&&dist[x]+g[y]>0) dist[y]=dist[x] + g[y]; } } for(j=0;j<m;j++) { int x=e[j].x, y=e[j].y; if(dist[y]<dist[x] + g[y]&&dist[x]+g[y]>0&&f[y][n]) return 1; //有负环回路 } return dist[n]>0;}int main(){ //freopen("test.txt","r",stdin); int i,j,k,t; while(scanf("%d",&n)!=EOF) { if(n==-1) break; m=0; memset(f,0,sizeof(f)); for(i=1;i<=n;i++) { scanf("%d%d",&g[i],&j); while(j--) { scanf("%d",&k); f[i][k]=1; e[m].x=i;e[m].y=k; m++; } } floyd(); if(!f[1][n]) { printf("hopeless\n"); continue; } if(bellman_ford(1)) printf("winnable\n"); else printf("hopeless\n"); } return 0;}
PS:我感觉写解题报告还是很有必要的。让自己去总结，弄明白解题思路。当然，也可以给别人提供一些思路。
hdu1317 XYZZY Floyd + Bellman_Ford
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。