HDU1317---HYZZY-阿里云开发者社区

HDU1317---HYZZY

2022-12-08 76

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： HDU1317---HYZZY

题目描述

输入样例

输出样例

hopeless
hopeless
winnable
winnable

思路:

题目的目的还是是求最长路径,刚开始有个初始的能量,每进入一个房间能量就会发生变化,最后判断到达终点时能量是否 > 0.

我们首先要判断这个图的连通性.因为如果初始点根本就和目的地不连通那么就无法到达,后序操作也毫无意义.

如果连通则判断是否有正环,对于正环,每走一次能量就会增多. 接着判断环上的点能否到达终点,如果可以则说明能到达,如果不能到达则说明这个环对我们来说是毫无意义的,到时我们不走,直接判断其他线路到终点时的能量情况即可.

如果没有环那就直接判断终点时的能量情况,大于0则说明可以到达,否则无法到达.

解题思路和注意点

参考代码

#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int maxn = 110;
int map[maxn][maxn],energy[maxn],reach[maxn][maxn],dis[maxn],vis[maxn],cnt[maxn],n;//map图,reach图:用于求连通性.  dis:走到该点的能量数组  energy:初始化后该点的能量数组  vis:标记是否在队列中  cnt:统计如队列的次数. 
void Floyd(){//求解图的连通性 
  for(int k = 1;k <=n;k++){
    for(int i = 1; i<= n;i++){
      for(int j = 1; j <= n; j++){
        if(reach[i][j]||(reach[i][k]&&reach[k][j])){
          reach[i][j] = 1;
        }
      }
    }
  }
} 
int SPFA(int u){
  queue<int> q;
  q.push(u);
  vis[u] = 1;
  dis[u] = 100;//初始能量为100 
  while(!q.empty()){
    int x = q.front();
    q.pop();
    vis[x] = 0;
    for(int i = 1; i <=n ;i++){
      if(map[x][i]&&dis[i] < dis[x]+energy[i]){
        dis[i] = dis[x]+energy[i];
        if(!vis[i]){
          cnt[i]++;
          if(cnt[i]>n){//如果有环,则判断环中的点是否可以到达终点  这里一定要结束,不然就会一直运行下去. 
            if(reach[x][n]){
              return 1;
            }else{//如果不能到达,就判断其在终点处的能量大小是否大于0. 
              return dis[n]>0;  
            } 
          }
          q.push(i);
          vis[i] = 1;
        }
      }
    }
  }
  return dis[n]>0; //如果没有则判断到终点是否还有能量. 
} 
int main()
{
  int num,v;
  while(cin>>n&&n!=-1){
    //数据初始化
    memset(map,0,sizeof(map));
    memset(reach,0,sizeof(reach));
    memset(energy,0,sizeof(energy));
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(cnt,0,sizeof(cnt));
    for(int i = 1; i <= n; i++){
      cin>>energy[i]>>num;
      for(int j = 1; j <= num; j++){//图中关系进行初始化 
        cin>>v;
        map[i][v] = 1;
        reach[i][v] = 1;
       }
     }
     Floyd();
     if(!reach[1][n]){
      cout<<"hopeless"<<endl;
      continue;
     } 
     if(SPFA(1)){//如果有正环,并且该环中的点能够到达终点 / 没有环但是最后到目的地的能量>0 则胜利 
      cout<<"winnable"<<endl;
     }else{
      cout<<"hopeless"<<endl;
     } 
  }
  return 0;
 }