<题目链接>
<转载于 >>> >
题目大意：
有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加。
货币的交换是可以重复多次的，所以我们需要找出是否存在正权回路，且最后得到的s金额是增加的
怎么找正权回路呢？（正权回路：在这一回路上，顶点的权值能不断增加即能一直进行松弛）
解题思路：
本题与bellman的目的刚好相反。即bellman本用于找负环，求最小路径，本题是利用同样的思想找正环，求最大路径，因此，改变一下初始化和松弛操作，再加上对正环的判定即可。
#include<iostream> using namespace std; int n; //货币种数 int m; //兑换点数量 int s; //持有第s种货币,表示哪个点，代表起点 double v; //持有的s货币的本金 int all; //边总数 double dis[101]; //s到各点的权值 class EDGE { public: int a; //货币a int b; //货币b double r; //rate double c; //手续费 }edge[202]; void add(int u,int v,double vala,double valb){ edge[all].a=u,edge[all].b=v,edge[all].r=vala,edge[all++].c=valb; } bool bellman() { memset(dis,0,sizeof(dis)); //这里与bellman的目的刚好相反。初始化为源点到各点距离无穷小 dis[s]=v; //即bellman本用于找负环，求最小路径，本题是利用同样的思想找正环，求最大路径 /*relax*/ bool flag; for(int i=1;i<=n-1;i++) { flag=false; for(int j=0;j<all;j++) if(dis[edge[j].b] < (dis[edge[j].a] - edge[j].c) * edge[j].r) //寻找最长路径 { //进行比较的是"某点到自身的权值"和"某点到另一点的权值" dis[edge[j].b] = (dis[edge[j].a] - edge[j].c) * edge[j].r; flag=true; } if(!flag) //如果不能更新了，就直接跳出 break; } /*Search Positive Circle*/ for(int k=0;k<all;k++) if(dis[edge[k].b] < (dis[edge[k].a] - edge[k].c) * edge[k].r) //正环能够无限松弛 return true; return false; } int main() { int a,b; double rab,cab,rba,cba; while(cin>>n>>m>>s>>v) { all=0; for(int i=0;i<m;i++) //构建无向边 { cin>>a>>b>>rab>>cab>>rba>>cba; add(a,b,rab,cab); add(b,a,rba,cba); } /*Bellman-form Algorithm*/ if(bellman()) //存在正环 cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
2018-08-27