poj-1860 Currency Exchange **
/** 汇率问题: Bellman_Ford算法 , 判断正环
*
* 有个奇怪的问题: 如果把 d初始化为 -inf 则 WA, 初始化为 0 或 -100 之类的值则AC~奇怪
*/
#include <iostream>
#include <cstring>
using namespace std;
const int maxN = 100 + 5;
int n, m, s;
double v, r, c, d;
void ini(){
for(int i=1; i<=n; i++)
d = 0;
d = v;
}
/*
bool relax(int lhs, int rhs){
double tmp = (d - c) * r;
if(tmp >= eps && d < tmp + eps){
d = tmp;
return 1;
}
return 0;
}
*/
bool Bellman_Ford(){
ini();
bool flag;
for(int i=1; i<=n; i++){
flag = 0;
for(int j=1; j<=n; j++){
for(int k=1; k<=n; k++){
if(r >= 0)
if(d < (d - c) * r){
d = (d - c) * r;
flag = 1;
}
}
}
if(!flag) break; //没有边能继续松弛
}
//判断正环
for(int j=1; j<=n; j++){
for(int k=1; k<=n; k++){
if(r >= 0 && d < (d - c) * r){
return 1;
}
}
}
return 0;
}
int main(){
while(cin >> n >> m >> s >> v){
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++)
r = -1;
int a, b;
for(int i=1; i<=m; i++){
cin >> a >>b;
cin >> r >> c >> r >> c;
}
if(Bellman_Ford())
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}
页:
[1]