E
题目大意：汇率问题，有N个银行，他们之间有一些汇率，某个人手里面拿着其中一种钱，然后在这里面兑换钱币，当然兑换是有汇率和手续费的，然后经过一系列兑换后问手里面的钱是不是能增加？
integer A and B - numbers of currencies it exchanges, and real R AB, C AB, R BA and C BA - ？
这句话是每行有6个数，前面两个数是AB货币，依次往后是AB之间的汇率，AB之间的交易税，BA之间的汇率，BA之间的交易税
貌似这题就是专门为了spfa设计的啊。。。。。只要判断手持的这种货币是否增长了就行。
/////////////////////////////////////////////////////////////////////////
想法没错，不过无情的错了一次，而且还找了很长时间的BUG，最终发现原来是公式写错了....计算汇率的时候应该先减去佣金在乘上汇率....全是泪
#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std;
const int maxn = 105;
const int oo = 0xfffffff;
struct node
{
int B;
double rate, commission;//汇率和佣金
node(int B, double r, double c):B(B),rate(r),commission(c){}
};
vector<node> G;
double v;
int spfa(int k, double m)
{
queue<int> Q;
Q.push(k);
while(Q.size())
{
int s = Q.front();
Q.pop();
int len = G.size();
for(int i=0; i<len; i++)
{
node q = G;
double p = (v-q.commission)*q.rate;
if(p > v)
{
v = p;
Q.push(q.B);
}
}
if(v > m)
return 1;
}
return 0;
}
int main()
{
int N, M, s;
double m;
while(scanf("%d%d%d%lf", &N, &M, &s, &m) != EOF)
{
int i;
for(i=1; i<=N; i++)
{
v = 0;
G.clear();
}
v = m;
int a, b;
double rab, cab, rba, cba;
for(i=0; i<M; i++)
{
scanf("%d%d%lf%lf%lf%lf", &a, &b, &rab, &cab, &rba, &cba);
G.push_back(node(b, rab, cab));
G.push_back(node(a, rba, cba));
}
int ans = spfa(s, m);
//printf("%lf\n", v);
if(ans == 1)
printf("YES\n");
else
printf("NO\n");
}
return 0; }
页:
[1]