题目连接
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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?