POJ1860Currency Exchange

POJ1860Currency Exchange

题意 ：有多种货币,货币之间可以交换,这需要手续费,当你用100A币交换B币时,A到B的汇率是29.75, 手续费是0.39,那么你可以得到(100-0.39)*29.75 = 2963.3975 B币 .问s币的金额经过交换最终得到的s币金额数能否增加. 货币的交换可以重复进行多次的.(每次交换,货币必须完全交换)

input: N:货币的种类数, M:货币之间可交换的关系数目(当成边 A币-B币 ), S:最开始的时候Nick拥有的货币的种类, V:最开始的时候Nick拥有的S类货币的数目. 

M行:

每行输入六个数据:

                  A: 类型为A的货币

                  B:类型为B的货币

                  R_AB: A币交换成B币的时候的汇率

                  C_AB: A币交换成B币的时候的手续费

                  R_BA and C_{BA  与上述相反}

分析: 货币种类当成点,两种货币的交换关系当成边, 则题目要求的可以解释为:  从S点的货币出发, 最终回到S点, 若S点货币增加则输出YES， 否则输出NO 。   可知 必定存在一个以S为起点也以S为终点的环, 且无限次循环此环的话, S点货币数目将一直增加, 所以, 我们只需判断以S为起点, 是否存在一个环,使得环的权值不断增大即可， 可用Bellman-Ford算法进行判断

BellMan-Ford算法详解

Code:

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int maxn = 105; struct node{ int u; int v; double ex; double w; }edge[maxn*2]; int len=0; int N, M, S; double V; void addedge(int u, int v, double ex, double w ){//存下每一条边 edge[len].u = u; edge[len].v = v; edge[len].ex = ex; edge[len].w = w; len++; return ; } double dis[maxn]; bool BellmanFord(int u, double w){ int i, j; memset(dis, 0, sizeof(dis)); dis[u] = w; for(i=1; i<=N; i++){ bool flag=false; for(j=0; j<len; j++){ if( dis[edge[j].v] < (dis[edge[j].u] - edge[j].w)*edge[j].ex ){ //判断是否可以更新dis值 dis[edge[j].v] = (dis[edge[j].u] - edge[j].w)*edge[j].ex; flag=true; } } if(!flag) break; } for(j=0; j<len; j++){//判断是否存在符合条件的环 if( dis[edge[j].v] < (dis[edge[j].u] - edge[j].w)*edge[j].ex ){ return true; } } return false; } int main() { while(~scanf("%d %d %d %lf", &N, &M, &S, &V)){ len=0; int u, v; double ex1, w1, ex2, w2; while(M--){ scanf("%d %d %lf %lf %lf %lf", &u, &v, &ex1, &w1, &ex2, &w2); addedge(u, v, ex1, w1); addedge(v, u, ex2, w2); } if(BellmanFord(S, V)){ printf("YES\n"); } else { printf("NO\n"); } } return 0; }