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

点击量：184

众所周知，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;
}