【解题报告】 POJ - 1860 Currency Exchange （spfa最短路）

原题地址

推荐博客

SPFA（Bellman-ford算法的队列优化）算法的实现及功能总结如下：

实现：

用一个dis数组来存每一个节点到源点的距离，开始时，将除源点外所有其他点的dis置为无穷大，源点的dis置为0，接着，将源点插入队列中。然后每次从队列中取一个节点u出来，遍历与它存在边的节点v，若dis[v] > dis[u] + w[u][v] （其中w[u][v]为u，v两条边的权值，则松弛dis[v]，若v不在队列中则插入队列。最终直至队列为空。

plus：队列操作执行完之后，就已经得到了dis数组中存储的为源点到每一个点的最短路径，如果此时再遍历每一条边，发现仍有dis[v]可以进行松弛操作，则说明该图中存在权值和为负的环。

功能：

• 求存在负边的单源最短路径
• 判断图中是否存在负环

好了，进入正题：

思路：

该题目正好和Bellman-Ford的思路逆着来，我们要判断一个图中是否存在权值为正的环，那么我们的解题思路不变，就是判断的条件完全反过来，本来求单元最短路应该是把s点的dis置为0， 我们要先把s点的dis置为v，即一开始他拥有的s货币的总数，然后经过一系列松弛操作之后我们判断是否能够得到dis[s]的值大于v就行了，要注意的是，我们初始化dis的时候就要把所有点的dis都置为0，然后判断松弛的时候应该要满足当前v的估计值大于由u转换为v得来的值。

（话说题目不是写着可能有重边的情况吗，为什么不考虑也AC了）

#include <iostream>
#include <queue>
using namespace std;
const static int maxn = 110;
double rate[maxn][maxn], commi[maxn][maxn];
int n, m, s;
double v;
double dis[maxn];
bool inque[maxn];
bool spfa(int start)
{
    queue <int> q;
    fill_n(dis, maxn, 0);
    q.push(start);
    inque[start] = true;
    dis[start] = v;
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        inque[u] = false;
        for(int i=1; i<=n; i++)
        {
            if(dis[i] < (dis[u]-commi[u][i])*rate[u][i])
            {
                dis[i] = (dis[u]-commi[u][i])*rate[u][i];
                if(!inque[i])
                {
                    q.push(i);
                    inque[i] = true;
                }

            }
        }
        if(dis[start] > v)
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>s>>v;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i == j)
                rate[i][j] = 1;
            else
                rate[i][j] = 0;
        }
    }
    while(m--)
    {
        int a, b;
        double rab, cab, rba, cba;
        cin>>a>>b>>rab>>cab>>rba>>cba;
        rate[a][b] = rab;
        commi[a][b] = cab;
        rate[b][a] = rba;
        commi[b][a] = cba;
    }
    if(spfa(s))
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}