小雪崩 发表于 2015-9-11 13:44:05

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]
查看完整版本: poj-1860 Currency Exchange **