如果从S到S存在一条正回路,那就说明,本金可以无限增加,即输出yes,所以这是一道求最长路径的题目,我们采用spfa算法计算是否存在正环即可。对于图,每个节点就是一种currency,我采用的是邻接链表的方式存储边,这是因为,对于A->B这条边有很多种,即这个图存在重边。

#include<iostream>
#include<vector>
#include<queue>
#include<list>
#include<cstring>
#include<algorithm>
using namespace std;
#define double float
struct edge
{
    int from;
    int to;
    double rate;
    double commission;
    edge(int f,int t,double r,double c)
    {
        from=f;
        to=t;
        rate=r;
        commission=c;
    }
};
list<edge> EdgeList[105];
double Cash[105];
int size_cur;
int size_poi;
int source;
double quantity;

bool spfa()
{
    int inQ[105];
    int num_change[105];
    memset(inQ,0,sizeof (inQ));
    memset(num_change,0,sizeof(num_change));
    queue<int> Q;
    Q.push(source);
    inQ[source]=1;
    while(!Q.empty())
    {
        int v=Q.front();
        Q.pop();
        inQ[v]=0;
        for(list<edge>::iterator i=EdgeList[v].begin();i!=EdgeList[v].end();i++)
        {
            edge e=*i;
            if(Cash[e.to]<(Cash[e.from]-e.commission)*e.rate)
            {
                Cash[e.to]=(Cash[e.from]-e.commission)*e.rate;
                if(inQ[e.to]==0)
                {
                    Q.push(e.to);
                    inQ[e.to]=1;
                    num_change[e.to]++;
                    if(num_change[e.to]>=size_cur)
                        return true;
                }
            }
        }
    }
    return false;
    
}

int main()
{
    memset(Cash,0,sizeof(Cash));
    cin>>size_cur>>size_poi>>source>>quantity;
    Cash[source]=quantity;
    for(int i=0;i<size_poi;i++)
    {
        int A,B;
        double r_ab,c_ab,r_ba,c_ba;
        cin>>A>>B>>r_ab>>c_ab>>r_ba>>c_ba;
        edge temp(A,B,r_ab,c_ab);
        EdgeList[A].push_back(temp);
        edge temp2(B,A,r_ba,c_ba);
        EdgeList[B].push_back(temp2);
    }
    cout<< (spfa()?"YES":"NO")<<endl;
    return 0;
}