poj1860--Currency Exchange

奇忠诚

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

/** \brief poj 1860 Bellman-Ford
*
* \param date 2014/7/24
* \param state AC
* \return memory 708K time 141ms
*
*/
#include <iostream>
#include <fstream>
#include <cstring>
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<allEdge;j++)
if(dis[Map[j].b] < (dis[Map[j].a]-Map[j].Com)*Map[j].rate)
{
dis[Map[j].b] = (dis[Map[j].a]-Map[j].Com)*Map[j].rate;
flag=true;
}
if(!flag)
break;
}
for(int k=0;k<allEdge;k++)
if(dis[Map[k].b] < (dis[Map[k].a]-Map[k].Com)*Map[k].rate)
return true;
return false;
}
int main()
{
//cout << &quot;Hello world!&quot; << endl;
//freopen(&quot;input.txt&quot;,&quot;r&quot;,stdin);
//while(scanf(&quot;%d %d %d %f&quot;,&N,&M,&S,&V)!=EOF)
while(cin>>N>>M>>S>>V)
{
allEdge=0;
for(int i=0;i<M;i++)
{
int a,b;
double Rab;
double Cab;
double Rba;
double Cba;
//cin>>a>>b>>Map[a].rate>>Map[a].Commission
//>>Map[a].rate>>Map[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<<&quot;YES&quot;<<endl;
else cout<<&quot;NO&quot;<<endl;
}
return 0;
}
转载请注明出处：http://blog.csdn.net/greenapple_shan/article/details/38307879