Bellman-ford算法的反向应用－－正循环检查

/** \brief poj 1860 Bellman-Ford * * \param date 2014/7/24 * \param state AC * \return memory 708K time 141ms * */#include 
     
      #include 
      
       #include 
       
        using namespace std;struct RateAndCom{//public:    int a;    int b;    double rate;    double Com;};//Map[MAXN];const int MAXN=101;RateAndCom Map[101*2];double dis[MAXN];int N;//货币种数int M;//兑换点数量int S;//持有第s种货币double V;//第s种货币本金int allEdge;bool Bellman_Ford(){    memset(dis,0,sizeof(dis));    dis[S]=V;    /*relax*/    bool flag;    for(int i=1;i<=N-1;i++)    {        flag=false;        for(int j=0;j
        
         >N>>M>>S>>V)    {        allEdge=0;        for(int i=0;i
         
          >a>>b>>Map[a][b].rate>>Map[a][b].Commission            //>>Map[b][a].rate>>Map[b][a].Commission;            cin>>a>>b>>Rab>>Cab>>Rba>>Cba;            Map[allEdge].a=a;            Map[allEdge].b=b;            Map[allEdge].rate=Rab;            Map[allEdge].Com=Cab;            allEdge++;            Map[allEdge].a=b;            Map[allEdge].b=a;            Map[allEdge].rate=Rba;            Map[allEdge].Com=Cba;            allEdge++;        }        //Bellman-Ford        if(Bellman_Ford())            cout<<"YES"<
         
        
       
      
     

转载请注明出处：