最初,一直在纠结后面大循环需要用2*n还是n+1次,考虑了只有某一个point具有显著盈利的exchange ratio时,最远返回到起始currency s的最坏情况。但后来看了别人的解答,才想到了,可能存在一个小的回路,exchange ratio盈利但是并不显著,那么这个需要的次数可能为正无穷,所以就要从是否有currency在某回路反复是否有增加的情况考虑。
后来WA了很多次,最后就只是把float改成double就过了。还没想通原因。。。题目中要求10-2<=rate<=102
#include<iostream>
#define MAXn 100
double quantity[MAXn+1];
int M1[MAXn];
int M2[MAXn];
double r[MAXn][4];
bool bellmanford(int n,int m,int s,double v)
{
bool flag;
for(int j=0;j<2*n;j++)
{
flag=true;
for(int i=0;i<m;i++)
{
if((quantity[M1[i]]-r[i][1])*r[i][0]>quantity[M2[i]])
{
flag=false;
quantity[M2[i]]=(quantity[M1[i]]-r[i][1])*r[i][0];
}
if((quantity[M2[i]]-r[i][3])*r[i][2]>quantity[M1[i]])
{
flag=false;
quantity[M1[i]]=(quantity[M2[i]]-r[i][3])*r[i][2];
}
}
if(flag)
{
if(quantity[s]>v)
{
flag=false;
return flag;
}
else
break;
}
}
for(int i=0;i<m;i++)
{
if((quantity[M1[i]]-r[i][1])*r[i][0]>quantity[M2[i]])
{
flag=false;
quantity[M2[i]]=(quantity[M1[i]]-r[i][1])*r[i][0];
}
if((quantity[M2[i]]-r[i][3])*r[i][2]>quantity[M1[i]])
{
flag=false;
quantity[M1[i]]=(quantity[M2[i]]-r[i][3])*r[i][2];
}
}
return flag;
}
int main()
{
int n,m,s;
double v;
scanf("%d%d%d%lf",&n,&m,&s,&v);
for(int i=0;i<n+1;i++)
quantity[i]=0;
quantity[s]=v;
int i=0;
int result=1;
while(i!=m)
{
scanf("%d%d%lf%lf%lf%lf",&M1[i],&M2[i],&r[i][0],
&r[i][1],&r[i][2],&r[i][3]);
i++;
}
if(bellmanford(n,m,s,v))
printf("NO\n");
else
printf("YES\n");
return 0;
}
分享到:
相关推荐
北大POJ1860-Currency Exchange【Bellman】 解题报告+AC代码
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码