三倍经验 P1931 UVA436 SP9340
题意
给你 \(n(n \le 30)\) 种货币及 \(m\) 种汇率,问是否出现套利的情况。
怎么没给 \(m\) 的范围啊
思路
首先把汇率抽象成一张图。容易发现,若一个单位的某种货币经过一个环获得了大于一的代价,说明出现了套利。具体来说,考虑 Floyd ,若 $\exists i\in n,f[i][i]\ge1 $ 则说明出现了套利的情况
code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
inline int read(){
int x=0,flag=1;char ch=getchar();
while(ch<'0' || ch>'9'){flag=(ch=='-')?-1:1;ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*flag;
}
inline bool read(int &n){
int x=0,flag=1;char ch=getchar();
while(ch<'0' || ch>'9'){flag=(ch=='-')?-1:1;ch=getchar();}
while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
n=x*flag;return n;
}
const int N=30+10;
const int M=1e3+10;
map<string,int> mp;
int n,m;
double f[N][N];
signed main(){
int Cnt=0;
while(read(n)){
memset(f,0,sizeof(f));
bool flag=false;
for(int i=1;i<=n;++i){string s;cin>>s;mp[s]=i;}
read(m);
for(int i=1;i<=m;++i){string u,v;double val;cin>>u>>val>>v;f[mp[u]][mp[v]]=val;}
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int k=1;k<=n;++k) f[i][j]=max(f[i][j],f[i][k]*f[k][j]);
for(int i=1;i<=n;++i) if(f[i][i]>1) flag=true;
cout<<"Case "<<++Cnt<<": "<<(flag?"Yes\n":"No\n");
}
return 0;
}
标签:ch,洛谷,int,题解,while,flag,P1931,include,define
From: https://www.cnblogs.com/dyyzy/p/17832724.html