HDU - 1317 ~ SPFA正权回路的判断-白红宇的个人博客

发布日期：2021-05-06 14:14:34 浏览次数：26 分类：精选文章

本文共 1402 字，大约阅读时间需要 4 分钟。

题意:有最多一百个房间，房间之间连通，到达另一个房间会消耗能量值或者增加能量值，求是否能从一号房间到达n号房间。

看数据，有定5个房间，下面有5行，第

i

行代表

i

号房间的信息，第一个数字表示从此房间到达连接的房间得到的能量，第二个数字表示连接的有几个房间，后面输出房间后。

思路： 正向去模拟，求出到达n点后尽可能的让dis[n]的值更大 , dis[1]初始化为100，其他初始化为零，因为在松弛的时候必须保证能量值大于零。

这里面说一下SPFA正权回路的判断，当一个点进入队列第n次的时候，说明存在正权回路（假设最坏的情况，其他n-1个点都会使这个点进入队列，若是进入n次，说明有回路）

为什么是最多进n-1次队列？

从1到n有n-1条边，对于一个顶点最多松弛n-1次！

注意： 本题需要注意dis数组初始化为0

看代码吧：

#include
   
    #include
    
     #include
     
      using namespace std;int cent[12010],u[12010],v[12010],w[12010],dis[12010],book[12010],first[12010],next1[12010];int k,j=0,n,m,l,t1,t2,inf=-0x3f3f3f3f;void SPFA(){       memset(cent,0,sizeof(cent));//计算点进入队列的次数    memset(book,0,sizeof(book));    memset(dis,0,sizeof(dis));    queue
      
       q;    book[1]=1;    dis[1]=100;    q.push(1);    while(!q.empty())    {           int p=q.front();        q.pop();        int k=first[p];        book[p]=0;        cent[p]++;        if(cent[p]>n)//找到负权回路        {               dis[p]=0x3f3f3f3f3f3f3f;            book[p]=1;//以后不进队列        }        while(k!=-1)        {               if(dis[v[k]]
       
        0)        printf("winnable\n");    else        printf("hopeless\n");}int main(){       while(~scanf("%d",&n)&&(n!=-1))    {           for(int i=0;i<=n;i++)            first[i]=-1;        k=0,j=0;        int t1,t2,t3;        for(int i=1;i<=n;i++)        {               scanf("%d%d",&t1,&t2);            for(int j=0;j

上一篇：POJ - 3660 传递闭包

下一篇：关于欧拉回路和欧拉道路

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章