poj1860 Currency Exchange(spfa判断是否存在正环)

题意：有m个货币交换点，每个点只能有两种货币的互相交换，且要给佣金，给定一开始的货币类型和货币数量，问若干次交换后能否让钱增加。

思路：spfa求最长路，判断是否存在正环，如果存在则钱可以在环中一直增加，最后的钱肯定也是增加的。

#include <iostream>

#include <cstring>

#include <queue>

#include <cstdio>

using namespace std;

const int maxn =  + ;

struct edge{

    int to, next;

    double r, c;

} ed[maxn*];

int n, m, s, inq[maxn];

int head[maxn], tot;

double v, dis[maxn];

bool vis[maxn];

inline void add( int u, int v, double r, double c ){

    ed[tot].to = v;

    ed[tot].r = r;

    ed[tot].c = c;

    ed[tot].next = head[u];

    head[u] = tot ++;

}

inline bool spfa(int start){

    queue<int> q;

    memset( vis, , sizeof(vis) );

    memset( dis, , sizeof(dis) );

    memset( inq, , sizeof(inq) );

    dis[s] = v;

    vis[s] = ;

    q.push(s);

    while( q.size() ){

         int u = q.front();

         q.pop();

         vis[u] = ;

         if( ++inq[u]>=n ) return ;    //一个点进队列的次数大于等于点的数量n则存在环

         for( int i=head[u]; i!=-; i=ed[i].next ){

             int v = ed[i].to;

             if( dis[v]<(dis[u]-ed[i].c)*ed[i].r ){

                 dis[v] = (dis[u]-ed[i].c)*ed[i].r;

                 if( !vis[v] ){

                     vis[v] = ;

                     q.push(v);

                 }

             }

         }

    }

    return ;

}

int main(){

    // freopen("in.txt", "r", stdin);

    scanf("%d%d%d%lf", &n, &m, &s, &v);

    memset( head, -, sizeof(head) );

    tot = ;

    for( int i=; i<m; i++ ){

        int u, v;

        double ru, cu, rv, cv;

        scanf("%d%d%lf%lf%lf%lf", &u, &v, &ru, &cu, &rv, &cv);

        add( u, v, ru, cu );

        add( v, u, rv, cv );

    }

    if( spfa(s) ) puts("YES");

    else puts("NO");

    return ;

}