以下是会用到题目的链接
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代码：
4.还有一个正权回路的相似问题 ：Arbitrage例题链接
京公网安备 11010502036488号