PKU ACM 1860 Bellman - Ford 算法-程序员宅基地

技术标签：算法 c ios

第一次接触 Bellman - Ford 算法。然后做了一个关于这个算法的题目，自己太水，搞了半天也没有AC，参考别人代码了，不过最后还算是敲出来了

算法概要：算法采用松弛技术，对图中的所有边做松弛，松弛一共使用了 {V}-1次，因为图中最长的那条边的长度可能是 {V}-1条，所以经过 {V{-1次松弛，所有的边，都能松弛到最佳状态

算法导论里，这个算法用来求解，最短路径的，这道题目稍加改造，每个点的值不是最短路径，而是经过若干次交换币种后所剩下的钱，松弛的策略是使得钱越来越多。

当松弛不下去的时候，说明没有+环，如果可以一直松弛，认为确实是由+环路，可以盈利

#include <iostream>
#include <fstream>
using namespace std;

struct Edge
{
	int a,b;
	double r,c;
};
double maxDistance[300];
bool bellman(int s,int n,int m,Edge *e,double v)
{
	int i,j;
	for( i = 0; i <= n; i++)
	{
		maxDistance[i] = -100000000;
	}
	maxDistance[s] = v;
	for( i = 0; i < n; i++)
	{
		bool stop = true;
		for( j = 0 ; j < m ; j++)
		{
			//从a到b b是目标点
			if(maxDistance[e[j].a] > 0 
				&& maxDistance[e[j].b] < (maxDistance[e[j].a] - e[j].c)*e[j].r)
			{
				maxDistance[e[j].b] = (maxDistance[e[j].a] - e[j].c)*e[j].r;
				stop = false;
			}
		}
		if(stop)
		{
			return false;
		}
	}
	return true;
}
int main()
{
	int n,m,s;
	int i,f,t;
	double fc,tc,fr,tr,v;
	Edge e[300];
	ifstream input;
	input.open("data.txt",std::ios::in);
	while(input>>n>>m>>s>>v)
	{
		for( i = 0; i < m; i++)
		{
			input>>f>>t>>fr>>fc>>tr>>tc;
			Edge e1 = {f,t,fr,fc};
			Edge e2 = {t,f,tr,tc};
			e[i] = e1;
			e[i+m] = e2;
		}
		if(bellman(s,n,2*m,e,v))
		{
			cout<<"YES"<<endl;
		}
		else
		{
			cout<<"NO"<<endl;
		}
	}
}

本文链接：https://blog.csdn.net/hopeztm/article/details/7021078

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

使用openlayers加载本地离线地图瓦片的一个最简单地例子_openlayer加载离线地图-程序员宅基地

文章浏览阅读1.8k次。上一篇文章写了 leaflet，本篇说一下openlayers。第一步，下载：https://github.com/openlayers/openlayers/releases/download/v6.2.1/v6.2.1-dist.zip解压后，我们只需要其中两个文件ol.css，ol.js第二步，下载瓦片，参考上篇文章，https://blog.csdn.net/netying..._openlayer加载离线地图

最全的HTTP响应状态码列表：除了404，HTTP状态码还有啥？-程序员宅基地

文章浏览阅读903次。HTTP是一个应用层协议，虽然在2015年已推出HTTP/2版本，并被主要的web浏览器和web服务器支持。它的主要特点可概括如下：支持客户/服务器模式。简单快速：..._除了404notfound还有什么

【算法训练营】周测1-程序员宅基地

文章浏览阅读1.7k次，点赞50次，收藏48次。驭风计划课程链接如果需要答案代码可以私聊博主有任何疑问或者问题，也欢迎私信博主，大家可以相互讨论交流哟~~

《从缺陷中学习C/C++》——6.3　数组传参时的sizeof-程序员宅基地

文章浏览阅读74次。本节书摘来自异步社区出版社《从缺陷中学习C/C++》一书中的第6章，第6.3节，作者：刘新浙 , 刘玲 , 王超 , 李敬娜 , ，更多章节内容可以访问云栖社区“异步社区”公众号查看。6.3　数组传参时的sizeof从缺陷中学习C/C++代码示例void copy(int a[], int b[]) {　　memcpy(b, a, sizeof..._void copy(int a[], int (&b)[]) { 　　memcpy(a, b, sizeof(b)); }

美式期权定价方法之最小二乘蒙特卡洛模拟（LSM）_最小二乘法期权定价-程序员宅基地

文章浏览阅读8.2k次，点赞5次，收藏47次。美式期权定价方法之最小二乘蒙特卡洛模拟前言前文对欧式期权的蒙特卡洛模拟定价方法进行了介绍和python量化，本章节主要是对前一章节的补充。也就是介绍美式期权的蒙特卡洛定价方法。一、美式期权不同于欧式期权，美式期权合约的行权时间是不固定的。美式期权(American option)是指可以在成交后有效期内任何一天被执行的期权。也就是指期权持有者可以在期权到期日以前的任何一个工作日，选择执行或不执行期权合约。美式期权允许期权持有者在到期日或到期日前执行购买(如果是看涨期权)或出售(如果是看跌期权)标_最小二乘法期权定价

【Composer】：Your requirements could not be resolved to an installable set of packages._composer your requirements could not be resolved t-程序员宅基地

文章浏览阅读1.5k次。错误内容vagrant@homestead:/usr/share/nginx/html/laravel-blog$ sudocomposerinstallLoadingcomposerrepositorieswithpackage informationInstallingdependencies (includingrequire-dev) fromlockfileYourrequirementscouldnot beresolvedto aninstallablesetofpackages. _composer your requirements could not be resolved to an installable set of pa

随便推点

微信小程序接收后端数据并显示轮播图_微信小程序轮播图后端-程序员宅基地

文章浏览阅读1.4k次。轮播图、是否自动轮播autoplay、修改轮播速度slider部分代码：index.wxml<view class="container" style="">  <swiper class="home-swiper" indicator-dots="true" autoplay="{{autoplay}}" interval="{{..._微信小程序轮播图后端

图书推荐|西门子S7-1200 PLC编程与应用实例-程序员宅基地

文章浏览阅读1.4k次，点赞26次，收藏16次。编撰而成，作者是行业专家，在自动控制领域有独特建树，从事过十余个行业的相关项目，因此，你从本书不仅可以学习PLC1200的应用，其中的工作和实践经验尤其难得。参与过智能制造、轨道交通、市政燃气、石油石化、智慧矿山、光伏发电、火力发电、钢铁冶金、医药制造等行业的项目，项目经验丰富。，也可供有一定基础的工程师借鉴和参考，还可作为高等院校自动化和机电专业的教材。用，基础配合实例，循序渐进，通俗易懂，内容详实且丰富，书中还在多个地方使用了。《西门子S7-1200 PLC编程与应用实例》内容由浅入深，由基础到应用，