首页 > 代码库 > POJ1860
POJ1860
题目链接:https://vjudge.net/problem/POJ-1860
解题思路:每种货币就是一个点,而兑换点其实就是边,由此组成图,求的是“最长路”。利用Bellman-Ford算法判断是否有正环。
AC代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 using namespace std; 5 const int maxn=105; 6 int vis[maxn]; 7 double d[maxn]; 8 int N,M,S,j; 9 double V; 10 struct edge{ 11 int from,to; 12 double rate,comm; 13 }es[maxn<<1]; 14 bool Bellman_Ford(){ 15 d[S]=V; 16 for(int i=1;i<N;i++){ 17 bool update=false; 18 for(int k=0;k<j;k++){ 19 edge temp=es[k]; 20 if(d[temp.to]<(d[temp.from]-temp.comm)*temp.rate){ 21 d[temp.to]=(d[temp.from]-temp.comm)*temp.rate; 22 update=true; 23 } 24 } 25 if(!update) 26 return false; //如果更新次数小于或等于N-1次,那么说明没有正环 27 } //如果没有正环,那么最多更新N-1次 28 for(int k=0;k<j;k++){ 29 edge temp=es[k]; 30 if(d[temp.to]<(d[temp.from]-temp.comm)*temp.rate){ 31 d[temp.to]=(d[temp.from]-temp.comm)*temp.rate; 32 return true; //如果能更新N次,那么说明有正环 33 } 34 } 35 return false; 36 } 37 int main(){ 38 scanf("%d%d%d%lf",&N,&M,&S,&V); 39 for(int i=1;i<=M;i++){ 40 scanf("%d%d",&es[j].from,&es[j].to); 41 scanf("%lf%lf",&es[j].rate,&es[j].comm); 42 j++; 43 scanf("%lf%lf",&es[j].rate,&es[j].comm); 44 es[j].from=es[j-1].to,es[j].to=es[j-1].from; 45 j++; 46 } 47 if(Bellman_Ford()) printf("YES\n"); 48 else printf("NO\n"); 49 return 0; 50 }
POJ1860
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。