spfa判负环 学习笔记【图论】【负环】

作者: wjyyy 分类: 学习笔记,负环 发布时间: 2018-06-22 19:32

点击量:32

 

众所周知,dijkstra基于贪心,是不能有负边权的,而Bellman-Ford可以。来自Bellman-Ford的SPFA同样可以优秀地判负环,我们介绍几种方案:

 

一、朴素做法:进队n次,则不满足。

因为Bellman-Ford是通过三角形不等式(\(dis[x]+v<dis[y]\)即更新)枚举每条边来更新的,而无层次感可言,同时SPFA的bfs也是。尽管用了队列优化,也不能清楚、方便地知道状态是怎么转移过来的。而对于同一个点,在经过n次松弛后,如果还能松弛,说明存在三角形不等式至少被用过两遍。而我们知道,最短路最多包括n-1条边,如果超过n-1条边,就说明有负环,还能继续更新这时我们把它掐掉 XD。也就是在松弛n次后,就一定存在负环,此时停止遍历,直接返回有负环状态。

二、优化做法1

在原来的spfa基础上,记录最短路的边数,每次更新最短路时更新这个值,(不是更新到较小值,是更新为转移过来的值),也就是对于边(u,v),如果这条边更新了最短路,那么就要更新cnt[v]=cnt[u]+1,如果cnt[v]≥n,就说明有负环。上一段提到如果当前找到的最短路包含n条边,说明它一定重复经过了某一个点,而这个点的其中一个入边属于负环,否则不可能更新更多次。

三、优化做法2

把原来的队列优化Bellman-Ford改为基于dfs的Bellman-Ford,也就是对于每个点的状态,我们通过dfs更新。因为dfs是一条最短路链,如果dfs迭代回此次dfs遍历过的点,那么说明最短路经过了一个点多次,那么根据松弛,这个点一定会被经过更多次,所以在负环上,这种做法比较简洁,不过要防止卡dfs时爆栈。

第一、三种方式的代码可以参照我写的小k的农场 题解。这里贴出第二种方式的代码。

Code:(luogu负环一题过不了?)

#include
#include
#include
using std::deque;
struct node
{
    int n,v;
    node *nxt;
    node(int n,int v)
    {
        this->n=n;
        this->v=v;
        nxt=NULL;
    }
    node()
    {
        nxt=NULL;
    }
};
node head[2100],*tail[2100];
int n;
int dis[2100],cnt[2100];
bool used[2100];
bool spfa(int x)
{
    memset(dis,0x3f,sizeof(dis));
    memset(used,0,sizeof(used));
    deque q;
    q.push_back(x);
    dis[x]=0;
    cnt[x]=1;
    used[x]=true;
    while(!q.empty())
    {
        int k=q.front();
        q.pop_front();
        used[k]=false;
        node *p=&head[k];
        while(p->nxt!=NULL)
        {
            p=p->nxt;
            if(p->v+dis[k]n])
            {
                dis[p->n]=p->v+dis[k];
                if(!used[p->n])
                {
                    used[p->n]=true;
                    cnt[p->n]=cnt[k]+1;
                    if(cnt[p->n]>=n)
                        return true;
                    if(q.empty()||dis[p->n]n);
                    else
                        q.push_back(p->n);
                }
            }

        }
    }
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    int m,u,v,w;
    while(T--)
    {
        memset(cnt,0,sizeof(cnt));
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            tail[i]=&head[i];
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            tail[u]->nxt=new node(v,w);
            tail[u]=tail[u]->nxt;
            if(w>=0)
            {
                tail[v]->nxt=new node(u,w);
                tail[v]=tail[v]->nxt;
            }
        }
        bool ans=false;
        for(int i=1;i<=n;i++)
            if(!cnt[i])
                ans|=spfa(i);
        if(ans)
            puts("YE5");
        else
            puts("N0");
    }
    return 0;
}

 

 

1
说点什么

avatar
1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
trackback

[…] 【spfa判负环学习笔记】怎么会有这么奇怪的东西 […]

/* */