题意:
一个图, 点权代表走到该点可获得的能量值. 可正可负. 一个人从1 号出发,带有100点能量. 问是否有一种方案可使人在能量值>0的时候走到n.
思路:
这个题首先要注意点权. 其实就是这点的所有入边的边权都等于这点的点权.
要找长路, 而非最短路. 但是可以借助最短路的算法SPFA求.
最短路的算法SFPA主要是 队列 + 松弛
松弛操作直接关系到我们运行算法的目的----求最短路
而队列的优化(相对于Bellman-Ford)则是把整个松弛操作放入了BFS的框架中, 主要是使得询问顺序合理, 而这种询问顺序是通用的, 与"最短路"并不是特殊匹配的.因此在这道题中尽管是为了找正环 or 最长路, 也是放在了SFPA的框架下.
啰嗦结束~
#include <cstdio>
#include <queue>
#include <cstring>
const int MAXN=110;
using namespace std;
int n;
int weight[MAXN];
int power[MAXN];
int _count[MAXN];//记录某点的入队列次数
bool map[MAXN][MAXN];
bool reach[MAXN][MAXN];//floyd判断任何两点是否可达 void Floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
reach[i][j]=(reach[i][j]
||(reach[i][k]&&reach[k][j]));
}
}
}
} bool SPFA(int now){///求最长路.和求最短路的核心完全不同.只是借助了SPFA对图广搜的流程,判断正环并且避免负环
queue<int>Q;
Q.push(now);
memset(power,0,sizeof(power));
memset(_count,0,sizeof(_count));
power[1]=100;
while(!Q.empty()){
int now=Q.front();
Q.pop();
_count[now]++;///统计该点入队次数
if(_count[now]>=n)return reach[now][n];//如果某个点的次数超过n次，那么说明存在正环，此时只要判断这点到n点是否可达就行了
for(int next=1;next<=n;next++){
if(map[now][next]&&power[now]+weight[next]>power[next]){
///第一次进入时,只要不死都可以进入.第二次进入该店则必有环,那么保证不进入负环或0环
Q.push(next);
power[next]=power[now]+weight[next];
}
}
}
return power[n]>0;
} int main(){
while(~scanf("%d",&n)&&n!=-1){
memset(map,false,sizeof(map));
memset(reach,false,sizeof(reach));
for(int i=1;i<=n;i++){
int num;
scanf("%d%d",&weight[i],&num);
for(int j=1;j<=num;j++){
int k;
scanf("%d",&k);
map[i][k]=true;///邻接矩阵
reach[i][k]=true;///bool可达矩阵
}
}
Floyd();
if(!reach[1][n]){
printf("hopeless\n");
}else {
if(SPFA(1)){
printf("winnable\n");
}else
printf("hopeless\n");
}
}
return 0;
}