设为首页 加入收藏

TOP

HDU 1317 XYZZY
2015-07-24 05:49:44 来源: 作者: 【大 中 小】 浏览:3次
Tags：HDU 1317 XYZZY

题意是指 从1 到 N 能否保证 到达每个点的时候 能量都为正数。


起点 1 初始100 点能量。

输入是 从 1 ~ N ， 分别是 能量，能到m个房间， 分别是 a1,a2,a3,…,am

可以给每个能到达的点 而 产生的边赋权，即能量值。


SPFA 求最长路的变形，出现负环不怕，出现正环就需要一点改动。

vis[]标记是否需要入队，d[] 表示能量，que[] 表示入队次数。

如果出现正环（que[v]>=n），表明一定能 保证到达每个点的时候都是正能量。

这时候直接 将 d[v] 赋最大值（因为可以一直循环获得正能量），并下一次的时候不再入队。


最后 d[n]>0 表明能行。

//C++ 0ms
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define INF 0xfffffff #define eps 1e-6 using namespace std; int n,m; struct lx { int v,en; }; vector
              
                g[101]; int d[101]; bool vis[101]; int que[101]; void SPFA() { for(int i=1; i<=n; i++) d[i]=-INF,vis[i]=0,que[i]=0; queue
               
                q; d[1]=100,vis[1]=1,que[1]=1; q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; if(que[u]>n)continue;// >= WA for(int j=0; j
                
                 0) { d[v]=d[u]+en; if(!vis[v]) { vis[v]=1; q.push(v); if(++que[v]>=n)d[v]=INF; } } } } if(d[n]>0)puts("winnable"); else puts("hopeless"); } int main() { while(scanf("%d",&n),n!=-1) { int en,v,u; for(int i=0; i<=n; i++) g[i].clear(); for(int i=1; i<=n; i++) { u=i; scanf("%d%d",&en,&m); lx now; now.en=en; while(m--) { scanf("%d",&v); now.v=v; g[u].push_back(now); } } SPFA(); } }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：Codeforces 442B Kolya and Tande.. 下一篇：Codeforces 443A Borya and Hanab..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: