解决正负权回路&& POJ1860 Currency Exchange &&POJ3259 Wormholes 【图论】【总结】

以下是会用到题目的链接

POJ1860 Currency Exchange

POJ3259 Wormhole

以下内容需要用到最短路的spfa算法

一、引言

在这之前的总结当中，总结过不少的最短路问题，现在又碰到了新的问题，正负权回路，为什么要用这两个题当做例题来引出来呢？是因为这两个题，一个为正权回路，另一个为负权回路，其实正负权回路的原理是一样的，不过用这两个题既能练习，又能加以区分正负权回路的关系。

二、正权回路

POJ1860 Currency Exchange

题目大意：给你几种货币，与其之间的汇率与之间的手续费，问能否通过一个算式-（当前的金额-手续费）*汇率，来赚到钱。

题目思路：假设一个a通过这个关系，首先变成5个b，五个b又通过这个关系又变成了7个a，所以经过一番转换a的数量就增加了。（7>5）。不妨想一想，这其中与最短路之间的联系。由a->b 可以变成 5b，b->a可以变成7a。我们在想一下最短路的更新条件：dis[u]+edge[i].w<dis[e]，其实我们在这里可以转化一下，(dis[u]-edge[i].cm)*edge[i].w，在这其中dis[u]是现在的金额，经过这个算式，dis[e]得到的是他转换后的金额。是不是有点豁然开朗？这个题目也就是把dis[e]当做了起始货币与当前货币交换，能得到的当前货币的金额。所以说我们只需要发现，这里面dis[e]可以无限增加，或者虽然不可以无限增加，但是到最后dis[1]大于最初的值了(这也就说明赚到钱了)，就可以输出YES了。

具体实现：我们要实现就需要把他当做一个最短路问题来看待，但是因为这个题目需要让钱能否无线增加，所以说，我们应该以最长路的问题去做，或者用大白话来说：正权回路用最长路，负权回路用最短路。至于为什么也是很容易证明的，dis[e]既然要无限增加，那么更新条件应该是dis[e]<x，负权路反之，所以以上结论是成立的。因为之前我们说过最短路有Spfa，dijkstra，floyd这几种算法，但是Dijkstra不适用于边有负权值，也就是说他可以解决正权回路而不能解决负权回路。所以为了保险起见，我们接下来，用两种算法实现：

1.Spfa 该算法之前博客中有总结过不再认真去总结直接上核心算法代码 spfa链接：图论的几种求最短路的方法 2.bellmanford 该算法适用于的点比较少，因为它基于动态规划的思想，但是代码简短，比较好写，所以读者自己选择。

3.个人比较喜欢spfa也就没有去钻研 bellman。

代码实现：

附上spfa的代码+注释：

int judge_spfa(int n,int s,double v)
{
    queue<int>q;
    for(int i=1;i<=n;i++) dis[i]=-1,vis[i]=0;
    dis[s]=v;
    q.push(s);//把每一种货币都做为一个起点看待。
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)//链式前向星
        {
            int e=edge[i].e;
            double x,y;
            x=(dis[u]-edge[i].commission)*edge[i].rate;//套上公式
            if(dis[e]-x<0)//最长路的判断
            {
                dis[e]=x;
                q.push(e);
                vis[e]++;
                if(vis[e]>n+1) return 1;//形成正负权回路的条件，大牛们总结得出，具体证明我也不会
            }
        }
    }
    if(vis[s]-v>0) return 1;//这个地方是比较容易忽略的，一般来说根据题目而定。
    return 0;
}

用链式前向星做的邻接表，也可以用邻接矩阵之前都总结过了链式前向星的链接链式前向星链接

这样这个题目也就结束了，总体而言这个正权回路还是比较好解的。

三、负权回路

POJ3259 Wormhole

题目大意：科学家发现有一些虫洞可以倒流时间，有些不可以，给你几组a-b之间双向的路表示从a到b需要c秒，其次给你几组单向的路表示，a到b可以倒流时间c秒，问可不可以让时间一直处于倒流的状态。

题目思路：这个题很明显是与上一个题相似的不过是正权变成负权，让倒流时间的边的权值设为负值，若出现负权回路，则说明可以一直倒流时间。根据之前总结的负权回路是最短路，所以初始化dis->INF。

代码实现：

spfa的代码+注释：

int judge_spfa(int n)
{
    for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=0;
    queue<int>q;
    dis[1]=0;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int e=edge[i].e;
            if(dis[e]>dis[u]+edge[i].w)
            {
                dis[e]=dis[u]+edge[i].w;
                q.push(e);
                vis[e]++;
                if(vis[e]>n+1) return 0;//已经形成负圈
            }
        }
    }
    return 1;//未形成负圈
}

四、总结

1.负权回路与正权回路这种算法，也可以适用于差分约束系统。

2.spfa时空优化是最大的，Spfa栈除外，然后又可以解决回路问题等，所以建议多多使用spfa，提高正确率。

3.最后附一下这两个题的AC代码：

POJ3259 Wormholes

POJ1860 Currency Exchange

4.还有一个正权回路的相似问题：Arbitrage例题链接