题意:

给出一些货币和货币之间的兑换比率,问是否可以使某种货币经过一些列兑换之后,货币值增加。

举例说就是1美元经过一些兑换之后,超过1美元。可以输出Yes,否则输出No。

分析:

首先我们要把货币之间的关系转化成一张图。转化时,用STL里面的map很方便。

为每种货币分配一个序列号,一个序列号代表了一个图中间的NODE,而node之间的edge用汇率表示。

一开始用Dijkstra算法做,死活AC不了,网友给的理由是:

由于Dijkstra算法不能处理带有负权值的最短路,但此题中,两种货币之间的兑换比率可能小于1,相当于这条路径的权值为负

前车之鉴,WA的代码:

#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
#include<string>
#include<map>
using namespace std;
#define maxn 31
#define inf 0x3f3f3f3f
double edges[maxn][maxn];
double dist[maxn];
typedef pair<int,int> P;
void init(){
for(int i=1;i<maxn;i++)
for(int j=1;j<maxn;j++)
edges[i][j]=(i==j?1:0);//1代表等价价换,0:代表无法交换
} void dijkstra(int s,int n){
bool visited[maxn];
memset(visited,0,sizeof(visited));
visited[s]=true;
for(int i=1;i<=n;i++)
dist[i]=edges[s][i];
for(int i=1,u;i<=n;i++){
double max=-1;
for(int j=1;j<=n;j++)
if(!visited[j]&&dist[j]>max){
max=dist[j]; u=j;
} visited[u]=true;
for(int j=1;j<=n;j++){
if(dist[u]*edges[u][j]>dist[j])
dist[j]=dist[u]*edges[u][j];
}
}
} int main(){
//freopen("in.txt","r",stdin);
int n,cases=0;
while(scanf("%d",&n)!=EOF && n){
cases++;
init();
map<string,int> ma;
string s,t;
for(int i=1;i<=n;i++){
cin>>s;
ma.insert(make_pair(s,i));
}
int m;
double tmp;
scanf("%d",&m);
while(m--){
cin>>s>>tmp>>t;
edges[ma[s]][ma[t]]=tmp;
} dijkstra(1,n);
printf("Case %d: ",cases);
if(dist[1]>1.0)
printf("Yes\n");
else
printf("No\n");
}
}

最后写了一个Floyd的代码版本,结果一下子就过了,我只能默默的哭了

#include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
#include<string>
#include<map>
using namespace std;
#define maxn 31
#define inf 0x3f3f3f3f
double edges[maxn][maxn];
void init(){
for(int i=1;i<maxn;i++)
for(int j=1;j<maxn;j++)
edges[i][j]=(i==j?1:0);//1:代表等价交换,0:代表无法交换
} void floyd_warshall(int s,int n){
for(int k=1;k<=n;k++){
for(int i=1,u;i<=n;i++){
for(int j=1;j<=n;j++){
if(edges[i][k]*edges[k][j]>edges[i][j])//如果找到了更好的交换方案
edges[i][j]=edges[i][k]*edges[k][j];
}
}
}
} int main(){
//freopen("in.txt","r",stdin);
int n,cases=0;
while(scanf("%d",&n)!=EOF && n){
cases++;
init();
map<string,int> ma;
string s,t;
for(int i=1;i<=n;i++){
cin>>s;
ma.insert(make_pair(s,i));
}
int m;
double tmp;
scanf("%d",&m);
while(m--){
cin>>s>>tmp>>t;
edges[ma[s]][ma[t]]=tmp;
} dijkstra(1,n);
printf("Case %d: ",cases);
/*for(int i=1,u;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%.2f ",edges[i][j]);
}
printf("\n");
}*/
if(edges[1][1]>1.0)
printf("Yes\n");
else
printf("No\n");
}
}

最后再用bellman_ford模板成功ac了一次。

 #include<iostream>
#include<cstdio>
#include<queue>
#include<string.h>
#include<string>
#include<map>
using namespace std; #define maxn 1000
#define inf 0x3f3f3f3f
struct edge{
int from;
int to;
float cost;
edge(){
from=0,to=0,cost=0;
}
edge(int a,int b ,float c){
from=a,to=b,cost=c;
}
};
edge Edges[maxn];
float dist[maxn];
void bellman_ford(int s,int V,int E){
for(int i=1;i<=V;i++)
dist[i]=0;
dist[s]=1.0;
for(int i=1;i<=V;i++){//这里可以改成while(true),但在有负权的情况下,会增加更多的循环,故建议照样例中写
bool update=false;
for(int j=1;j<=E;j++){
edge e=Edges[j];
if(dist[e.to]<dist[e.from]*e.cost){
dist[e.to]=dist[e.from]*e.cost;
update=true;
}
}
if(!update)break;//一旦在某次循环中,不能再更新当前dist,那么就能提前结束该算法,break之
}
} void init(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j) Edges[i]=edge(i,j,1.0);//初始化,1:等价交换
else Edges[i]=edge(i,j,0); //0:无法交换
}
}
} int main(){
//freopen("in.txt","r",stdin);
int n,cases=0;
while(scanf("%d",&n)!=EOF && n){
cases++;
init(n);
map<string,int> ma;
string s,t;
for(int i=1;i<=n;i++){
cin>>s;
ma.insert(make_pair(s,i)); //构造字符串与数值的映射关系
}
int m;
double tmp;
scanf("%d",&m);
for(int i=1;i<=m;i++){
cin>>s>>tmp>>t;
Edges[i]=edge(ma[s],ma[t],tmp);
} bellman_ford(1,n,m);
printf("Case %d: ",cases);
if(dist[1]>1.0)
printf("Yes\n");
else
printf("No\n");
}
}

【问题】:Folyd算法能处理包含负权边的图吗?

答案是可以的。Floyd-Warshall算法和Bellman-Ford算法一样,可以处理边是负数的情况。

---《挑战程序设计竞赛》 P.103

POJ 2240 - Arbitrage(bellman_ford & floyd)的更多相关文章

  1. poj 2240 Arbitrage(Bellman_ford变形)

    题目链接:http://poj.org/problem?id=2240 题目就是要通过还钱涨自己的本钱最后还能换回到自己原来的钱种. 就是判一下有没有负环那么就直接用bellman_ford来判断有没 ...

  2. POJ 2240 Arbitrage(Floyed-Warshall算法)

    题意:给出n种货币,m种兑换比率(一种货币兑换为另一种货币的比率),判断测试用例中套汇是否可行.(套汇的意思就是在经过一系列的货币兑换之后,是否可以获利.例如:货币i→货币j→货币i,这样兑换后,是否 ...

  3. POJ 2240 Arbitrage(SPFA+邻接矩阵)

    ( ̄▽ ̄)" #include<iostream> #include<cstdio> #include<cmath> #include<algori ...

  4. poj 2240 Arbitrage (Floyd)

    链接:poj 2240 题意:首先给出N中货币,然后给出了这N种货币之间的兑换的兑换率. 如 USDollar 0.5 BritishPound 表示 :1 USDollar兑换成0.5 Britis ...

  5. POJ 3259 Wormholes (Bellman_ford算法)

    题目链接:http://poj.org/problem?id=3259 Wormholes Time Limit: 2000MS   Memory Limit: 65536K Total Submis ...

  6. POJ 2240 Arbitrage(floyd)

    http://poj.org/problem?id=2240 题意 : 好吧,又是一个换钱的题:套利是利用货币汇率的差异进行的货币转换,例如用1美元购买0.5英镑,1英镑可以购买10法郎,一法郎可以购 ...

  7. POJ 2240 Arbitrage(判正环)

    http://poj.org/problem?id=2240 题意:货币兑换,判断最否是否能获利. 思路:又是货币兑换题,Belloman-ford和floyd算法都可以的. #include< ...

  8. POJ 2240 Arbitrage (求负环)

    Arbitrage 题目链接: http://acm.hust.edu.cn/vjudge/contest/122685#problem/I Description Arbitrage is the ...

  9. POJ 2240 Arbitrage (Bellman Ford判正环)

    Arbitrage Time Limit: 1000MS   Memory Limit: 65536K Total Submissions:27167   Accepted: 11440 Descri ...

随机推荐

  1. clr 元数据

    clr相关编译器编译生成的托管模块由四部分组成:PE32或32+头.clr头.元数据.IL代码. 元数据和IL代码完全对应,保持一致(:>)性. 元数据有很多用途: VS的智能感知,自动补全: ...

  2. R 中同步进行的多组比较的包:npmc

    方差检验可以评估组间的差异.依据检验的结果,虽然你可以拒绝不存在差异的原假设,但方差检验并没有告诉你哪些组显著地与其他组有不同.Robert 在 <R in Action>一书中推荐了一个 ...

  3. Cent Os 常用操作

    开放端口 编辑iptables文件(/etc/sysconfig/iptables) -A INPUT -m state --state NEW -m tcp -p tcp --dport xx端口号 ...

  4. 常用html元素的取值和赋值方法总结

    1.获得type类型为TEXT或者AREATEXT的值 var textval = $("#text_id").attr("value"); var textv ...

  5. CSS——图片替换方法比较

    图片替换主要是指将文字替换成图片的技术,即在html语句中使用文字,浏览器显示时用对应的图片显示.其意义在于便于做网站优化(SEO),文字才是搜索引擎寻找的主要对象. 经典的替换方法: Fahrner ...

  6. jsp+servlet+javaBean+Dao

    一.Servlet程序各模块介绍1.JSP 用于显示.收集数据的部分.2.Servlet 用于验证数据.实例化JavaBean.调用DAO连接数据库.控制页面跳转3.DAO 用于连接数据库及进行数据库 ...

  7. java反射获取Object的属性和值

    在看反射顺便做个笔记,目前知道的反射的Object都是要有对象的也就是实体Bean. import java.lang.reflect.Field; import java.util.ArrayLis ...

  8. Dubbo入门---搭建一个最简单的Demo框架(转)

    Dubbo背景和简介 Dubbo开始于电商系统,因此在这里先从电商系统的演变讲起. 单一应用框架(ORM) 当网站流量很小时,只需一个应用,将所有功能如下单支付等都部署在一起,以减少部署节点和成本.  ...

  9. windows程序设计 基础

    API全名(Application Program Interface) Windows窗口主函数 int WINAPI WinMain( HINSTANCE hInstance,//应用程序本次运行 ...

  10. vue中使用全局函数

    方法一: 在mian.js中写入函数: Vue.prototype.bb = function () {        alert('OK'); } 然后在任何组件中都可以调用: this.bb() ...