pku 1860 Currency Exchange 第一周训练_最短路 spfa

宇文氏

　　http://poj.org/problem?id=186
　　题意就是转化成求最短路的模型，不过这里是求最长应该。以前做最短路基本上都是用Dijkstra()对于其他几个算法没有弄的明白，所以做起来比较吃力。。。
　　简介：
　　SPFA(Shortest Path Faster Algorithm)
是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，
并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
　　SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中
一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本
身被改进，于是再次用来改进其它的点，这样反复迭代下去。
　　判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
　　题解：


两种情况Yes，一种是存在正权回路，一种是求最长路后，实现了增值，也是Yes

用spfa来判断是否存在正权回路，其实spfa是可以用来判断是否存在回路的，不管是正权还是负权，只不过它们松弛的条件不同，正权的话，我们是往dis[]权值增大的方向松弛，负权的话，我们是往dis[]权值减少的方向松弛，然后判断是否存在回路只要看有没有一点入队列的次数大于n就行了

View Code


#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define maxn 107
#define inf 0x7fffffff
#define eps 1e-8
using namespace std;
int ct[maxn];
double r[maxn][maxn],c[maxn][maxn],dis[maxn],v;
bool visit[maxn];
int n,m,s;
bool spfa()
{
    queue<int>q;
    while (!q.empty()) q.pop();
    dis = v;
    q.push(s);
    visit = true; ct++;//ct统计入队次数
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        for (int i = 1; i <= n; ++i)
        {
            if ( (dis - c)*r - dis  > eps)//松弛所有U的子节点
            {
                dis = (dis - c)*r;//进行松弛，注意这里千万不要写到if里面，
                //才开始自己理解不好，就写到里面去了。。悲剧
                if (!visit)//判断是否在队列中，然后入队
                {
                    visit = true;
                    q.push(i);
                    if (++ct > n) return true;
                }
            }
        }
        visit = false;//把根节点标为未入队，因为后面的节点可能还会更新他这是与bfs的区别
    }
    if (dis - v > eps) return true;
    else return false;
}
int main()
{
    int i,j;
    for (i = 0; i < maxn; ++i)
    {
        visit = false;
        ct = 0; dis = 0;
        for (j = 0; j < maxn; ++j)
        {
            r[j] = c[j] = 0;
        }
    }
    scanf("%d%d%d%lf",&n,&m,&s,&v);
    int a,b;
    for (i = 0; i < m; ++i)
    {
        scanf("%d%d",&a,&b);
        scanf("%lf%lf%lf%lf",&r[a],&c[a],&r[a],&c[a]);//建图
    }
    if (spfa()) printf("YES\n");
    else        printf("NO\n");
}
　　Bellmen_Ford方法实现 《学习连接http://www.wutianqi.com/?p=1912》
　　ellman－Ford算法可以大致分为三个部分
第一，初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
第二，进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
第三，遍历途中所有的边（edge（u，v）），判断是否存在这样情况：
d（v） > d (u) + w(u,v)
则返回false，表示途中存在从源点可达的权为负的回路。

之所以需要第三部分的原因，是因为，如果存在从源点可达的权为负的回路。则 应为无法收敛而导致不能求出最短路径。



View Code


#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1007
#define eps 1e-8
using namespace std;
struct node
{
    int x,y;
    double r,c;
}g[maxn];
double dis[107];
int n,m,s,len;
double v;
bool bellman_ford()
{
    int i,j;
    for (i = 0; i <= n; ++i)
    dis = -1.0;
    dis = v;
    int flag = 0;
    for (i = 1; i < n; ++i)//松弛，注意这里去掉原点共n-1个点
    {
        for (j = 0; j < 2*m; ++j)
        {
            if ((dis[g[j].x ]- g[j].c)*g[j].r - dis[g[j].y] > eps)//这里是往个最大松弛
            dis[g[j].y] = (dis[g[j].x] - g[j].c)*g[j].r;
        }
    }
    for (i = 1; i < n; ++i)//检查是否存权为正的回路
    {
        for (j = 0; j < 2*m; ++j)
        {
            if ((dis[g[j].x] - g[j].c)*g[j].r - dis[g[j].y] > eps)
            {
                flag = 1;
                break;
            }
        }
    }
    if (flag || dis - v > eps) return true;//如果存在权为正的回路
    //且松弛后金钱数量增多
    else return false;
}
int main()
{
    int i,x,y;
   while (~scanf("%d%d%d%lf",&n,&m,&s,&v))
   {
       len = 0;
       for (i = 0; i < m; ++i)//见图，以边建
       {
           scanf("%d%d",&x,&y);
           g[len].x = x;
           g[len].y = y;
           scanf("%lf%lf",&g[len].r,&g[len].c);
           len++;
           g[len].x = y;
           g[len].y = x;
           scanf("%lf%lf",&g[len].r,&g[len].c);
           len++;
       }
       if (bellman_ford()) printf("YES\n");
        else                printf("NO\n");
   }
    return 0;
}