首页 > 代码库 > poj2240（Arbitrage）
poj2240（Arbitrage）
题目大意：
给你各国的货币名称，和国家与国家之间兑换的汇率，问你通过一系列的兑换能否是自己的财富增加。
解题思路：
先建图，因为给的是字符串不是阿拉伯数之间的联系，所以建图可以用map<string，int>mp 建图。赋值给结构体中的u，v。然后利用bellman—ford算法，因为如果财富能够通过兑换增值说明会有一条正权回路。所以利用bellman—ford算法 判断是否出现正权回路说明可以增值否则NO。
代码：
#include <algorithm>#include <iostream>#include <sstream>#include <cstdlib>#include <cstring>#include <cstdio>#include <string>#include <bitset>#include <vector>#include <queue>#include <stack>#include <cmath>#include <list>#include <map>#include <set>using namespace std;/***************************************/#define ll long long#define int64 __int64/***************************************/const int INF = 0x7f7f7f7f;const double eps = 1e-8;const double PIE=acos(-1.0);const int dx[]= {0,-1,0,1};const int dy[]= {1,0,-1,0};const int fx[]= {-1,-1,-1,0,0,1,1,1};const int fy[]= {-1,0,1,-1,1,-1,0,1};/***************************************/void openfile(){ freopen("data.in","rb",stdin); freopen("data.out","wb",stdout);}/**********************华丽丽的分割线,以上为模板部分*****************/const int MAX=-1;#define N 1000int t,edgenum;double w;typedef struct Edge{ int u,v; double cost;} Edge;Edge edge[N];double dis[N];bool Bellman_ford(){ int i,j; for(i=1;i<=t;i++) dis[i]=MAX; dis[1]=1; for(i=1;i<=t-1;i++) for(j=1;j<=edgenum;j++) if (dis[edge[j].v]<dis[edge[j].u]*edge[j].cost) dis[edge[j].v]=dis[edge[j].u]*edge[j].cost; int flag=0; for(i=1;i<=edgenum;i++) if (dis[edge[i].v]<dis[edge[i].u]*edge[i].cost) { flag=1; break; } return flag;}int main(){ int cas=0; while(scanf("%d",&t)&&t) { map<string,int>mp; char a[50],b[50]; int i,j; int num=0; for(i=0;i<t;i++) scanf("%s",a); scanf("%d",&edgenum); for(i=1;i<=edgenum;i++) { scanf("%s %lf %s",a,&w,b); if (mp[a]==0) mp[a]=++num; if (mp[b]==0) mp[b]=++num; edge[i].u=mp[a]; edge[i].v=mp[b]; edge[i].cost=w; } if (Bellman_ford()) printf("Case %d: Yes\n",++cas); else printf("Case %d: No\n",++cas); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。