POJ - 1860 Currency Exchange解题报告

    xiaoxiao2021-03-26  16

    Bellman-Ford 算法描述:

    1.创建源顶点 v 到图中所有顶点的距离的集合 distSet,为图中的所有顶点指定一个距离值,

    初始均为 Infinite,源顶点距离为 0;

    2.计算最短路径,执行 V - 1 次遍历;对于图中的每条边:如果起点 u 的距离 d 加上边的权值 w 小于终点 v 的距离 d,则更新终点v 的距离值 d;

    3.检测图中是否有负权边形成了环,遍历图中的所有边,计算 u 至 v 的距离,如果对于 v 存在更小的距离,则说明存在环;

     

    题目大意:

    很久以前看见的题目没做,因为是英文不想看,今天还是做了:

    题意:一个城市里有很多货币兑换点,每个兑换点可以兑换不同的货币,比如说a兑换b有一个兑换率r,还有一个手续费c,那么有价值v的a货币兑换成b货币就有(a-c)*r。现在输入n,m,s,v;表示有n种货币,m个兑换点,刚开始拥有的货币种类编号为s,价值为v。每个兑换点输入a,b,Rab,Cab,Rba,Cba,这个兑换点用a兑换b和b兑换a的兑换率和手续费。

     

    #include #include #include #define N 1500 #define inf 99999 using namespace std; double r[N][N];//兑换率 double c[N][N];//手续费 double w[N];//原钱数换成i号钱之后的单位数 int is[N][N]={0};//表示是否能换 void input(int n,int m,int s,double v) { for(int i=0;i >a>>b; cin>>r[a][b]>>c[a][b]>>r[b][a]>>c[b][a]; is[a][b]=1;//a到b能换 is[b][a]=1; } } void solve(int n,int m,int s,double v)//n种货币,m个兑换点,货币种类编号为s,价值为v。 { /*for(int i=1;i<=n;i++)//自己和自己能换 { is[i][i]=1; }*/ /*for(int i=1;i<=n;i++) { if(is[s][i]==1) { w[i]=(v-c[s][i])*r[s][i]; } }*/ for(int i=1;i v)cout<<"YES"< >n>>m>>s>>v; for(int i=0;i<=n;i++)//距离初始化成 { w[i]=-1000000; } w[s]=v; input(n,m,s,v); solve(n,m,s,v); output(n,m,s,v); return 0; }

    显然(虽然这个词不太好):有正权环则yes,负权环或者无环no!!!!

     

    前几次wa了:关于为什么一定要重新循环一次看看能不能再松弛,而不能看循环之后看w[s]是不是大于v,是因为,有可能s并不在环里面,而且循环次数不一定足够能更新到s。

     

    另注:cin>>a>>b>>r[a][b]>>c[a][b]>>r[b][a]>>c[b][a];会runtime error;不知道为什么。

    转载请注明原文地址: https://ju.6miu.com/read-650034.html

    最新回复(0)