POJ - 2240 Arbitrage SPFA判断负环+map

2024-03-29 09:18

本文主要是介绍POJ - 2240 Arbitrage SPFA判断负环+map,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

POJ-2240

题意

给定n种货币,m种交换关系,问是否能增值

解法

跟POJ - 1860一个揍性,利用SPFA判断正环即可。货币直接输入的名字,用map建立映射就可以了。POJ-1860

代码
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include<iostream>
#include<map>
#include<queue>
#include<cstring>  
#define endl "\n"
using namespace std;typedef long long ll;const int maxn=50;const int maxe=5050;const int inf=0x3f3f3f3f;struct Edge{int v,next;double w;}edge[maxe];int head[maxn],cnt;bool vis[maxn];//是否在队列 int in[maxn];//更新了多少次 double dis[maxn];int n,m;queue<int>q;int test; void init(){memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(in,0,sizeof(in));memset(dis,0,sizeof(dis));cnt=0;}void add(int u,int v,double w){edge[cnt].v=v;edge[cnt].next=head[u];edge[cnt].w=w;head[u]=cnt;cnt++;}bool spfa(int s) {q.push(s);vis[s]=true;in[s]++;dis[s]=1000;while(q.size()) {int p=q.front();q.pop();vis[p]=false;for(int i=head[p];i!=-1;i=edge[i].next) { //SPFAint v=edge[i].v;if(dis[v]<edge[i].w*dis[p]) {dis[v]=edge[i].w*dis[p];in[v]++;if(in[v]>=n)return true;//这个点更新了多于n次,说明存在负环 if(!vis[v]) {vis[v]=true;q.push(v);}}}}return false;}map<string,int>mp;int main(){IOSwhile(cin>>n&&n){init();for(int i=1;i<=n;i++){string s;cin>>s;mp[s]=i;}cin>>m;while(m--){int u,v;double w;string s1,s2;cin>>s1>>w>>s2;add(mp[s1],mp[s2],w);}cout<<"Case "<<++test<<": ";if(spfa(1))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}} 

这篇关于POJ - 2240 Arbitrage SPFA判断负环+map的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/858206

相关文章

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Java中Map.Entry()含义及方法使用代码

《Java中Map.Entry()含义及方法使用代码》:本文主要介绍Java中Map.Entry()含义及方法使用的相关资料,Map.Entry是Java中Map的静态内部接口,用于表示键值对,其... 目录前言 Map.Entry作用核心方法常见使用场景1. 遍历 Map 的所有键值对2. 直接修改 Ma

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》:本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时,需要提供方将Map类型的数据序列化为co

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

Java使用Stream流的Lambda语法进行List转Map的操作方式

《Java使用Stream流的Lambda语法进行List转Map的操作方式》:本文主要介绍Java使用Stream流的Lambda语法进行List转Map的操作方式,具有很好的参考价值,希望对大... 目录背景Stream流的Lambda语法应用实例1、定义要操作的UserDto2、ListChina编程转成M

判断PyTorch是GPU版还是CPU版的方法小结

《判断PyTorch是GPU版还是CPU版的方法小结》PyTorch作为当前最流行的深度学习框架之一,支持在CPU和GPU(NVIDIACUDA)上运行,所以对于深度学习开发者来说,正确识别PyTor... 目录前言为什么需要区分GPU和CPU版本?性能差异硬件要求如何检查PyTorch版本?方法1:使用命

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa