首页 > 其他分享 >套利(spfa判环+STL)

套利(spfa判环+STL)

时间:2024-05-23 22:59:19浏览次数:22  
标签:判环 idx BritishPound STL FrenchFranc int spfa include USDollar

套利

题目描述

套利是利用汇率差异实现货币增值。例如,1美元可以兑换0.5英镑、1英镑可以兑换10法郎、1法郎可以兑换0.21美元。接下来,一个聪明的交易商就可以从1美元开始,0.5 * 10.0 * 0.21 =1.05美元,获得了5%的利润。

你的任务是写一个程序,从输入文件读入汇率清单,然后决定套利是有可能的或没有可能的。

输入格式

输入文件包含多组数据,每组数据的第一行是一个整数n( 1<=n<=30 )。代表有多少种货币。接下来n行字符串,每行表示一种货币的名称(名称中不会出现空格)。下一行是一个整数m,约定了汇率表的长度。随后的m行中,每行有三部分组成。The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible. 每组数据之间空一行。当n=0时表示输入数据结束。

输出格式

第i组数据,输出Case i: 后,如果可以套利,输出Yes,否则输出No。

样例 #1

样例输入 #1

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

样例输出 #1

Case 1: Yes
Case 2: No

思路

这里是把我们之前做的题目把数字改成了字符串,其实本质上也一样,我们只要用map来装就行了。

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>

using namespace std;

const int N = 1e5;

double dist[N];
map<string,int>s;
int n,m;
bool st[N];
int e[N],ne[N],h[N],idx;
double w[N];
int cnt[N];
int T;

void add(int a,int b,double c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool spfa(){
    queue<int>q;
    
    memset(st,0,sizeof st);
    memset(dist,0,sizeof dist);
    memset(cnt,0,sizeof cnt);
    
    // dist[1]=1;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
        dist[i]=1;
    }
    
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            
            if(dist[j]<dist[t]*w[i]){
                dist[j]=dist[t]*w[i];
                cnt[j]=cnt[t]+1;
                if(!st[j]){
                    if(cnt[j]>=n)return false;
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    
    return true;
}

int main(){
    while(cin>>n,n){
        
        s.clear();
        idx=0;
        
        memset(h,-1,sizeof h);
        
        for(int i=1;i<=n;i++){
            string a;
            cin>>a;
            s[a]=i;
        }
        cin>>m;
        
        for(int i=1;i<=m;i++){
            string pa,pb;
            double x;
            cin>>pa>>x>>pb;
            int a=s[pa],b=s[pb];
            // cout<<a<<" "<<b<<endl;
            add(a,b,x);
            // add(b,a,x);
        }
        
        
        if(!spfa()){
            printf("Case %d: Yes\n",++T);
        }else{
            printf("Case %d: No\n",++T);
        }
        
    }
    
    return 0;
}

标签:判环,idx,BritishPound,STL,FrenchFranc,int,spfa,include,USDollar
From: https://blog.csdn.net/m0_60738889/article/details/139131614

相关文章

  • [USACO06DEC] Wormholes G(spfa判断环)
    [USACO06DEC]WormholesG题目背景英文题面见此链接题目描述John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边,并可以使你返回到过去的一个时刻(相对你进入虫洞之前)。John的每个农场有m......
  • c++实现的小型stl中遇到的问题
    friendstd::ostream&operator<<(std::ostream&ot,constList&lis);参数表中第一个ot应该是引用,因为std::ostream是不可复制的,只能通过引用进行传递,以确保正确的流传递和状态维护。要访问类的私有成员时,非成员函数重载运算符必须声明为友元函数因为参数表中第一个ot是引......
  • STL | string
    string介绍c++支持两种类型的字符串,一以NULL结尾的c风格字符串;二string类型的字符串头文件string是basic_string类模板使用char特化的类型#include<string>typedefbasic_string<char,char_traits<char>,allocator<char>>string;初始化//默认string对象,长度为0str......
  • STL | vector操作总结
    vector随机访问在序列末尾插入和删除元素为常量时间,而在中间插入和删除元素需要线性时间介绍vector为可变长的数组(动态数组),定义的vector数组可以随时添加和删除元素当vector容量不足以容纳新增元素时会扩容为两倍(不同编译器有不同的实现,GCC以两倍扩容),需要将元素复制到新开辟......
  • SPFA
    这算是我的第一篇使用LaTeX的文章易写,支持负权,可判负环,可以求最短路,也可以最长路,什么都行。就是容易被卡qwq所以SPFA他死了。是Bellman_Ford算法的队列优化版。使用范围支持负权,可以处理负环,可判负环,可以求最短路,也可以求最长路。平均时间复杂度\(O(m)\),极限时间复杂度为\(......
  • 有关c++STL容器及头文件
    万能头打遍天下无敌手(除了vjudge)#include<bits/stdc++.h>通用函数(在以下STL容器中均适用)size返回容器的实际长度(元素个数)empty返回一个bool型,表示容器是非为空vector声明:vector<int>头文件:Here#include<vector>一些函数:clear清空迭代器与b......
  • 【基础】一些新的STL
    Reduce(C++17)lls=reduce(a+1,a+1+n);//求和lls=reduce(a+1,a+1+n,std::plus<ll>);//求和doubles=reduce(a+1,a+1+n,std::multiples<double>);//求积ints=reduce(a+1,a+1+n,std::max<int>);/......
  • STL练习
    C++标准模板库(STL,StandardTemplateLibrary):包含一些常用数据结构与算法的模板的C++软件库。其包含四个组件——算法(Algorithms)、容器(Containers)、仿函数(Functors)、迭代器(Iterators).示例:算法:sort(a.begin(),a.end())容器:priority_queue<int>pque仿函数......
  • STL空间配置器
    在C++里,当我们调用new和delete进行对象的创建和销毁的时候,也同时会有内存配置操作和释放操作:这其中的new和delete都包含两阶段操作:对于new来说,编译器会先调用::operatornew分配内存;然后调用Obj::Obj()构造对象内容。对于delete来说,编译器会先调用Obj::......
  • C++ STL -- HashTable
    HashTable一般常用的unordered_set、unordered_map都是基于哈希表实现的,哈希表主要需要注意的是哈希冲突,迭代器等基础哈希映射使用哈希函数将键映射到索引的数据结构。即将原始数组索引通过哈希函数映射到一个哈希值上,从而将一个大范围索引,减小到一个小的固定范围哈希冲突......