$$\color{Purple}{kuangbin题解目录}$$
描述
某国家流通有 $N$ 种货币,编号 $1 \\sim N$。
该国家设有 $M$ 个货币兑换点,每个兑换点提供两种货币之间的兑换业务。
每个兑换点都自行设定货币兑换汇率以及服务费。
每个兑换点的基本信息可以用 $6$ 个数字 $A,B,R_{AB},C_{AB},R_{BA},C_{BA}$ 来描述,表示该兑换点提供第 $A$ 种货币和第 $B$ 种货币之间的相互兑换,并且从 $A$ 兑换到 $B$ 的兑换汇率为 $R_{AB}$,服务费为 $C_{AB}$,从 $B$ 兑换到 $A$ 的兑换汇率为 $R_{BA}$,服务费为 $C_{BA}$。
$A$ 到 $B$ 的兑换汇率就是 $1$ 单位 $A$ 货币可以换得的 $B$ 货币的数量。
服务费必须在兑换之前,先行从来源货币处扣除。
例如,如果从 $A$ 兑换 $B$ 的兑换汇率为 $29.75$,服务费为 $0.39$,则用 $100$ 元 $A$ 货币可以兑换 $(100 - 0.39) \* 29.75 = 2963.3975$ 元 $B$ 货币。
一个商人目前手上有 $V$ 元 $S$ 货币,他想要通过先将自己手中的钱进行辗转兑换,最终再次换回 $S$ 货币的方式,让自己手中的钱变得更多。
请你判断他能否做到。
输入格式
第一行包含四个数字 $N,M,S,V$。
接下来 $M$ 行,每行包含 $6$ 个数字 $A,B,R_{AB},C_{AB},R_{BA},C_{BA}$。
输出格式
如果可以做到让钱变多,则输出 YES
,否则输出 NO
。
数据范围
$1 \\le S \\le N \\le 100$,
$1 \\le M \\le 100$,
$0 \\le V \\le 1000$,
汇率取值范围 $\[10^{-2},10^2\]$,
服务费取值范围 $\[0,100\]$。
输入样例:
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00
输出样例:
YES
思路
货币种类
是点,货币交换
是边,能否在交换回来使得金钱变多,即是否存在正环
;- 可通过跑两次
floyd算法
,第一次$floyd$后算出每一种货币种类的金钱数
,第二次$floyd$后与第一次进行比较,若任意一个货币种类的金钱数变多则说明存在正环;- 可通过
spfa算法
求正环,注意初始距离为无穷小
($-\infty$),当松弛
过$n$次以上证明存在正环
.
代码
floyd算法
// Problem: 货币兑换
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4245/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-25 14:07:12
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 110
using namespace std;
typedef long long ll;
int n,m,start;
double money;
double rate[MAXN][MAXN];
double cost[MAXN][MAXN];
double dist[MAXN];
double backup[MAXN];
void floyd()
{
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dist[j]=max(dist[j],(dist[i]-cost[i][j])*rate[i][j]);
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> m >> start >> money;
for(int i=1;i<=m;i++)
{
int a,b;
cin >> a >> b;
cin >> rate[a][b] >> cost[a][b] >> rate[b][a] >> cost[b][a];
}
dist[start]=money;
floyd();
for(int i=1;i<=n;i++)
backup[i]=dist[i];
floyd();
int flag=0;
for(int i=1;i<=n;i++)
if(dist[i]>backup[i])
{
flag=1;
break;
}
if(flag==1)
cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
spfa算法
// Problem: 货币兑换
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4245/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-25 14:29:21
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 110
using namespace std;
typedef long long ll;
typedef pair<double,double> PDD;
const double eps=1e-8;
int n,m,start;
double money;
int head[MAXN],ed[2*MAXN],nex[2*MAXN],idx;
PDD val[2*MAXN];
double dist[MAXN];
int vis[MAXN],cnt[MAXN];
void add(int a,int b,PDD c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int spfa()
{
queue<int> q;
q.push(start);
vis[start]=1;
while(q.size()>0)
{
int temp=q.front();
q.pop();
vis[temp]=0;
for(int i=head[temp];i!=-1;i=nex[i])
{
double rate=val[i].first,cost=val[i].second;
int j=ed[i];
if(dist[j]+eps<(dist[temp]-cost)*rate)
{
dist[j]=(dist[temp]-cost)*rate;
cnt[j]=cnt[temp]+1;
if(cnt[j]>=n)
return 1;
if(vis[j]==0)
{
vis[j]=1;
q.push(j);
}
}
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> n >> m >> start >> money;
memset(head,-1,sizeof(head));
memset(dist,-0x3f,sizeof(dist));
for(int i=1;i<=m;i++)
{
int a,b;
double rate1,rate2,cost1,cost2;
cin >> a >> b >> rate1 >> cost1 >> rate2 >> cost2;
add(a,b,make_pair(rate1,cost1));
add(b,a,make_pair(rate2,cost2));
}
dist[start]=money;
if(spfa()==1)
cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}