您当前的位置: 首页 > 

MangataTS

暂无认证

  • 0浏览

    0关注

    423博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

AcWing 4242. 货币兑换(SPFA or Bellman 判正权环)

MangataTS 发布时间:2022-02-18 21:21:12 ,浏览量:0

题目连接

https://www.acwing.com/problem/content/description/4245/ http://poj.org/problem?id=1860

思路

根据题意我们可以知道,我们想求的是这个图中是否存在一个正权回路,让我们的钱变多了,那么我们建边的时候存储的信息就是终点v兑换汇率r服务费c,初始的时候我们有V这么多的S货币,那么我们就看其能转化为其他不同的货币使得下一个点的货币数量增加(一开始除了S点的货币为v其余初始化为小于等于0),那么最后如果某一个点更新了n次那么说明出现了一个正权环,使得我们的钱变多了,那么对于判断是否存在正权图我们可以用SPFA或者Bellman或者Floyd算法进行运算

代码
#include
#include
#include
#include
#include
#include
using namespace std;

const int N = 1e2+10;

struct Node{
	int v;
	double r,c;
};
vector E[N];
int n,m,s;
int cnt[N];
double dis[N],v;
bool vis[N];

void spfa(){
	dis[s] = v;
	queue que;
	que.push(s);
	while(!que.empty()){
		int t = que.front();
		que.pop();
		vis[t] = false;
		for(int i = 0,l = E[t].size();i             
关注
打赏
1665836431
查看更多评论
1.2927s