输入:
3 2 1 20.0 1 2 1.00 1.00 1.00 1.00 2 3 1.10 1.00 1.10 1.00
输出
YES
思路:有多种货币,货币之间可以进行交换,这就需要佣金,同时货币交换之间还存在着汇率.
如下图所示20A币交换成B币,之后得到的就是(20-1) * 1.00 = 19B, B货币也可以继续进行交换,转换成C货币.题目求的是S币经过交换之后最终能够增加.
货币的交换是多次的,而且货币的交换是双向的,能换过去,就能换回来.所以我们要求的是图中是否存在正权回路,这样的话,每转一圈货币数就会增加.
怎么找正权回路呢?
我们有三种方法:
Bellman-Ford方法.
SPFA (其实就是Bellman-Ford的优化算法)
DFS深搜(在深搜过程中回溯看能不能回到曾经的点)
参考代码:
#include<iostream> #include<string.h> using namespace std; const int maxn = 100+10; struct node { int u,v; double r,c;//佣金:c 汇率r } e[maxn * 2]; double dis[maxn],cnt; int n,m,s,num,flag; void add(int u,int v,double r,double c) { e[num].u = u; e[num].v= v; e[num].r = r; e[num].c = c; num++; } bool bellman_ford() { memset(dis,0,sizeof(dis)); dis[s] = cnt; for(int i = 1; i < n; i++) { flag = 0; for(int j = 0; j < num; j++) { if(dis[e[j].v] < (dis[e[j].u] - e[j].c)*e[j].r) { dis[e[j].v] = (dis[e[j].u] - e[j].c)*e[j].r; flag = 1; } } if(!flag) { //如果某一轮dis不再发生更新,则说明dis已更新完毕. return false; } } for(int j = 0; j < num; j++) { if(dis[e[j].v] < (dis[e[j].u] - e[j].c)*e[j].r) { //如果在第n次时还进行更新,则说明 出现了正环. return true; } } return false; } int main() { cin>>n>>m>>s>>cnt; int u,v; double r1,c1,r2,c2; while(m--){ cin>>u>>v>>c1>>r1>>c2>>r2; add(u,v,c1,r1); add(v,u,c2,r2); } if(bellman_ford()){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } return 0; }
