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"<
       
        转载请注明出处：http://blog.csdn.net/greenapple_shan/article/details/38307879