【POJ 1860】Currency Exchange

tongyi007

　　【题目链接】:http://poj.org/problem?id=1860
　　【题意】



给你n种货币,m种货币之间的交换信息;

交换信息以

A,B,RA,CA,RB,CB的形式给出;

即A换B的话假设A有x元则换成B就变成(X-CA)*RA

B换成A的话同理;

然后你一开始只有某一种x货币;

问你可不可能通过换货币来获得更多x货币;

即最后又要换回来.


　　【题解】



可以在做SPFA的最长路的时候判断能不能出现环.

具体的。

只要从x出去了,然后又回来了;

就说明能够在经过某些路径之后这个x又变大了;

任意哪一个x都可以;

因为你可以通过这条路径让x变得无穷大;

那么起点s肯定也能无穷大啦;

判断环的话只要判断一个点是否入队n次就好;



【Number Of WA】



1



【完整代码】

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int N = 110;
const int INF = 0x3f3f3f3f;
struct abc
{
int en;
double r,c;
};
int n,m,s,num[N];
bool inq[N];
double dis[N];
vector <abc> G[N];
queue <int> dl;
int main()
{
//freopen("F:\\rush.txt","r",stdin);
memset(dis,-INF,sizeof dis);
cin >> n >> m >> s;cin >> dis;
for (int i = 1;i <= m;i++)
{
int x,y;
double r,c;
abc temp;
cin >>x >> y >> r >> c;
temp.r = r,temp.c = c,temp.en = y;
G[x].push_back(temp);
cin >> r >> c;
temp.r = r,temp.c = c,temp.en = x;
G[y].push_back(temp);
}
dl.push(s);
num=1;
inq = true;
while (!dl.empty())
{
int x = dl.front();
inq[x] = false;
dl.pop();
int len = G[x].size();
for (int i = 0;i <= len-1;i++)
{
abc temp1 = G[x];
int y = temp1.en;
double ju = (dis[x]-temp1.c)*temp1.r;
if (ju>0)
{
if (dis[y]<ju)
{
dis[y] = ju;
if (!inq[y])
{
num[y]++;
if (num[y]>n)
return cout <<"YES"<<endl,0;
dl.push(y);
inq[y]=true;
}
}
}
}
}
cout <<"NO"<<endl;
return 0;
}