首页 > 代码库 > poj 1860
poj 1860
题意:给定N中货币 两种货币之间可以兑换 并且收取一定的费用 问 给定你一种货币与数量 是否能兑换到原来的货币 使自己的货币增加
思路:用bellman算法 判断是否有回路不断的增大;
?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | #include<iostream> #include<cstring> using namespace std; struct Node { int u,v; double ruv; double need; }e[500]; int n,s,m; double v; int all; double dist[111]; bool bellman() { int i,j; memset (dist,0, sizeof (dist)); dist[s]=v; for (i=0;i<n;i++) { for (j=0;j<all;j++) { if (dist[e[j].v]<(dist[e[j].u]-e[j].need)*e[j].ruv) dist[e[j].v]=(dist[e[j].u]-e[j].need)*e[j].ruv; } } for (j=0;j<all;j++) { if (dist[e[j].v]<(dist[e[j].u]-e[j].need)*e[j].ruv) break ; } if (j<all) return true ; return false ; } int main() { int i; int x,y; double nxy,cxy,nyx,cyx; while (cin>>n>>m>>s>>v) { all=0; for (i=0;i<m;i++) { cin>>x>>y>>cxy>>nxy>>cyx>>nyx; e[all].u=x;e[all].v=y;e[all].ruv=cxy;e[all++].need=nxy; e[all].u=y;e[all].v=x;e[all].ruv=cyx;e[all++].need=nyx; } if (bellman()) cout<< "YES" <<endl; else cout<< "NO" <<endl; } return 0; } |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。