Wandai Blog 共被围观 1,801,396 次

我看维基百科的介绍, 加上iceboy某次给我的讲解, 写出来了一个。

SPFA 是一种很简单而且很快的算法用来求单源最短路(就是在一个有向图里面, 从一个点出发, 到达所有点的最短路径)。

需要的数据结构有一个数组和一个存有图的数组的数组(也叫做二维数组)。

数组里面存的是目前的解。

比如有 1 2 3 4 5 五个顶点从 1 出发, 那么数组里是 0 ∞ ∞ ∞ ∞

然后还需要一个队列, 把初始节点1放到队列里, 就可以开始 SPFA 了!

过程是这样的, 每次从队列里取出一个顶点。

然后枚举这个顶点的所有边。

如果能够找到一个更好的解, 就更新那个数组, 同时把被更新的点放到队列里。 //貌似叫做”松弛操作”

如果队列什么都没有了, 说明完成了。

就是这样。

这个题目就是判断有没有负权回路。

判断有没有负权回路只需要判断某点进入队列的次数, 大于n-1就说明存在负权回路。

下面这段代码是可以AC的, 那就不管别的了>_<。

#include<iostream>
#include<queue>
using namespace std;
const int oo=0xFFFFFFF;
int G[600][600],n,m,w;
void init()
{
    cin>>n>>m>>w;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            G[i][j]=oo;
    int s,e,t;
    for(int i=1;i<=m;++i)
    {
        cin>>s>>e>>t;
        G[e][s]=G[s][e]=min(G[s][e],t);
    }
    for(int i=1;i<=w;++i)
    {
        cin>>s>>e>>t;
        t=-t;
        G[s][e]=min(G[s][e],t);
    }
}
bool SPFA()
{
    int ln[600],counter[600];
    bool inqueue[600];
    queue<int> Q;
    for(int i=1;i<=n;++i)
    {
        ln[i]=0;           //有一个神奇的点, 使得它到每个点距离为0
        Q.push(i);
        counter[i]=1;
        inqueue[i]=true;
    }
    while(!Q.empty())
    {
        int index=Q.front();
        Q.pop();
        inqueue[index]=false;
        for(int i=1;i<=n;++i)
        {
            if(ln[index]+G[index][i]<ln[i])
            {
                ln[i]=ln[index]+G[index][i];
                if(!inqueue[i])   //原来这里用stl的find函数, 结果TLE了=w=
                {
                    Q.push(i);
                    ++counter[i];
                    inqueue[i]=true;
                    if(counter[i]>n-1)
                        return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int F;
    cin>>F;
    while(F--)
    {
        init();
        cout<<(SPFA()?"YES":"NO")<<endl;
    }
    return 0;
}

话说为什么在poj上用G++和C++得到的结果不一样, 它们分别用了什么编译器, 求解。

然后Mrw神牛看到了这篇文章, 吐槽了我的邻接矩阵(int G[600][600]), 告诉我有邻接表这么个东西。

于是修改代码如下

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int oo=0xFFFFFFF;

class edge
{
    public:
        int v, ln;
        edge() : v(0), ln(0) {}
        edge(int v, int ln) : v(v), ln(ln) {}
};

int n,m,w;
vector<edge> G[600];
void init()
{
    cin>>n>>m>>w;
    for(int i=1;i<=n;++i)
    {
        G[i].clear();
    }

    int s,e,t;
    for(int i=1;i<=m;++i)
    {
        cin>>s>>e>>t;
        G[s].push_back(edge(e,t));
        G[e].push_back(edge(s,t));
    }
    for(int i=1;i<=w;++i)
    {
        cin>>s>>e>>t;
        G[s].push_back(edge(e,-t));
    }
}
bool SPFA()
{
    int ln[600],counter[600];
    bool inqueue[600];
    queue<int> Q;
    for(int i=1;i<=n;++i)
    {
        ln[i]=0;
        Q.push(i);
        counter[i]=1;
        inqueue[i]=true;
    }
    while(!Q.empty())
    {
        int index=Q.front();
        Q.pop();
        inqueue[index]=false;
        for(vector<edge>::iterator it=G[index].begin();it<G[index].end();++it)
        {
            if(ln[index]+it->ln<ln[it->v])
            {
                ln[it->v]=ln[index]+it->ln;
                if(!inqueue[it->v])
                {
                    Q.push(it->v);
                    ++counter[it->v];
                    inqueue[it->v]=true;
                    if(counter[it->v]>n-1)
                        return true;
                }
            }
        }
    }
    return false;
}
int main()
{
    int F;
    cin>>F;
    while(F--)
    {
        init();
        cout<<(SPFA()?"YES":"NO")<<endl;
    }
    return 0;
}

于是评测结果