【POJ 1860】Currency Exchange
【题目链接】: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;
bool inq;
double dis;
vector <abc> G;
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.push_back(temp);
cin >> r >> c;
temp.r = r,temp.c = c,temp.en = x;
G.push_back(temp);
}
dl.push(s);
num=1;
inq = true;
while (!dl.empty())
{
int x = dl.front();
inq = false;
dl.pop();
int len = G.size();
for (int i = 0;i <= len-1;i++)
{
abc temp1 = G;
int y = temp1.en;
double ju = (dis-temp1.c)*temp1.r;
if (ju>0)
{
if (dis<ju)
{
dis = ju;
if (!inq)
{
num++;
if (num>n)
return cout <<"YES"<<endl,0;
dl.push(y);
inq=true;
}
}
}
}
}
cout <<"NO"<<endl;
return 0;
}
页:
[1]