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;
const int MAXN=101;
RateAndCom Map;
double dis;
int N;//货币种数
int M;//兑换点数量
int S;//持有第s种货币
double V;//第s种货币本金
int allEdge;
bool Bellman_Ford()
{
memset(dis,0,sizeof(dis));
dis=V;
/*relax*/
bool flag;
for(int i=1;i<=N-1;i++)
{
flag=false;
for(int j=0;j<allEdge;j++)
if(dis.b] < (dis.a]-Map.Com)*Map.rate)
{
dis.b] = (dis.a]-Map.Com)*Map.rate;
flag=true;
}
if(!flag)
break;
}
for(int k=0;k<allEdge;k++)
if(dis.b] < (dis.a]-Map.Com)*Map.rate)
return true;
return false;
}
int main()
{
//cout << "Hello world!" << endl;
//freopen("input.txt","r",stdin);
//while(scanf("%d %d %d %f",&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.rate>>Map.Commission
//>>Map.rate>>Map.Commission;
cin>>a>>b>>Rab>>Cab>>Rba>>Cba;
Map.a=a;
Map.b=b;
Map.rate=Rab;
Map.Com=Cab;
allEdge++;
Map.a=b;
Map.b=a;
Map.rate=Rba;
Map.Com=Cba;
allEdge++;
}
//Bellman-Ford
if(Bellman_Ford())
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
转载请注明出处：http://blog.csdn.net/greenapple_shan/article/details/38307879
页:
[1]