POJ - 2240 Arbitrage SPFA判断负环+map

本文主要是介绍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;}}