美文网首页
Currency Exchange POJ - 1860

Currency Exchange POJ - 1860

作者: ChenKL | 来源:发表于2018-05-20 22:14 被阅读0次

    题意:币种兑换寻找是否有正环

    计算公式 (money - Cost) * Rate

    思路:spfa_dfs 判正环

    #include<stdio.h>
    #include<string.h>
    #include <vector>
    using namespace std;
    const int MAX_V = 200;
    struct edge {int to;
                 double Rate,C;};
    vector<edge> G[MAX_V];
    bool instack[MAX_V];
    double d[MAX_V];
    int V;
    bool spfa_dfs(int s){
      instack[s] = true;
      for (int i = 0;i<G[s].size();i++){
        edge e = G[s][i];
        if (d[e.to] < (d[s] -e.C) * e.Rate){
          d[e.to] = (d[s] - e.C) * e.Rate;
          if (!instack[e.to]){
            if (spfa_dfs(e.to)) return true;
          } else{
            return true;
          }
    
        }
      }
      instack[s] = false;
      return false;
    }
    int main()
    {
      double money;
      int M,S;
      scanf("%d%d%d%lf",&V,&M,&S,&money);
      for (int i = 0;i<M;i++){
        int  u,v;
        double Ruv,Cuv,Rvu,Cvu;
        scanf("%d%d%lf%lf%lf%lf",&u,&v,&Ruv,&Cuv,&Rvu,&Cvu);
        G[u].push_back(edge{v,Ruv,Cuv});
        G[v].push_back(edge{u,Rvu,Cvu});
      }
      memset(d,0,sizeof d);
      memset(instack,0,sizeof instack);
      d[S] = money;
      if (spfa_dfs(S))
        printf("YES\n");
      else
        printf("NO\n");
      return 0;
    }
    

    相关文章

      网友评论

          本文标题:Currency Exchange POJ - 1860

          本文链接:https://www.haomeiwen.com/subject/ruhxjftx.html