UVA 558 SPFA 判断负环

这个承认自己没看懂题目，一开始以为题意是形成环路之后走一圈不会产生负值就输出，原来就是判断负环，用SPFA很好用，运用队列，在判断负环的时候，用一个数组专门保存某个点的访问次数，超过了N次即可断定有负环（其实我觉得=N次了就可以断定了，当然这样是保险起见）。。。。别人还有用SPFA+DFS做的，还效率相当高，我还没怎么弄明白是怎么回事。。。还有，我突然想到讲最短路的时候说迪杰斯特拉不能用于有负权的图，这是为什么。。我还没想明白，先去睡觉吧。。。。

关于dijstla为什么不能有负权，昨晚躺下之后就想明白了，dijstla最大特性在于其把当前d值最小的点给灰化了，下次不用再访问了，而负权如果存在，将使得已经发生灰化的点，d值会变小，这样就不得不取消灰化，但一旦取消，dijstla就永远无法走到终点，（将一直在d值最小的那个点徘徊），因此spfa通过用队列把d值发生变化的点加进去，因而解决了这个问题这只是题外话，不用说太多

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

using namespace std;

int u[],v[],w[],next[],first[];

int d[],vis[],num[];

int n,m,cnt,flag;

void addedge(int a,int b,int c)

{

    u[cnt]=a;

    v[cnt]=b;

    w[cnt]=c;

    next[cnt]=first[a];

    first[a]=cnt++;

}

void spfa()

{

    int i,j;

    flag=;

    for (i=;i<=n;i++)

        d[i]=(<<);

    memset(vis,,sizeof vis);

    memset(num,,sizeof num);

    d[]=;

    queue <int> q;

    q.push();

    vis[]=;

    while (!q.empty())

    {

        int t=q.front();

        q.pop();

        vis[t]=;

        for (j=first[t];j>=;j=next[j])

        {

            int newnode=v[j];

            num[newnode]++;

            if (num[newnode]>n){

                   flag=;

                    return;

            }

            if (d[newnode]>d[t]+w[j])

            {

                d[newnode]=d[t]+w[j];

                //cout<<newnode<<" "<<d[newnode]<<endl;

                if (!vis[newnode]){

                    q.push(newnode);

                    vis[newnode]=;

             }

            }

        }

    }

}

int main()

{

    int t,i,j;

    scanf("%d",&t);

    while (t--)

    {

        cnt=;

        memset(first,-,sizeof first);

        scanf("%d%d",&n,&m);

        int a,b,c;

        for (i=;i<=m;i++){

          scanf("%d%d%d",&a,&b,&c);

          addedge(a,b,c);

        }

        spfa();

        if (!flag)

            puts("not possible");

        else

            puts("possible");

    }

    return ;

}

巴特西

UVA 558 SPFA 判断负环

最新文章

热门文章