学步园

题意：有N种货币 M个交换点，每个交换点提供 a，b两种货币的交换 汇率为rate 手续费为commission；假设你持有一种货币（S） 面值V；

让你去交换其他货币，如果你能找到一个交换路径 使得你的钱一直在增加 则输出YES 否则 输出NO；

思路：设货币 为 点， 交换点为 边； （现有货币-手续费） *汇率 为边的关系函数；题意即求 最长路径 判断 图 是否存在 正权回路；

逆 利用 bellman 算法 ：http://blog.csdn.net/jun_sky/article/details/7014446

#include <iostream>
using namespace std;
const int M = 105;
double dis[M];
int m,n,s;
double v;
struct Edge
{
	int a,b;
	double r,c; 
}e[M*2];
bool bellman_ford()
{
	int i,j;
	memset(dis, 0, sizeof(dis));
	dis[s] = v;
	for(i=1; i<n; i++)
	{
		bool flag = false;
		for(j=1; j<=2*m; j++)
		{
			if(dis[e[j].b] < (dis[e[j].a]-e[j].c)*e[j].r)
			{
				dis[e[j].b] = (dis[e[j].a]-e[j].c)*e[j].r;
				flag = true;
			}
		}
		if(!flag) break;
	}
	for(i=1; i<=2*m; i++)
	{
		if(dis[e[i].b] < (dis[e[i].a]-e[i].c)*e[i].r)
			return true;
	}
	return false;
}
int main()
{
	int i;
	scanf("%d %d %d %lf", &n, &m, &s, &v);
	for(i=1; i<=m; i++)
	{
		scanf("%d %d", &e[i].a, &e[i].b);
		scanf("%lf %lf", &e[i].r, &e[i].c);
		e[i+m].a = e[i].b; e[i+m].b=e[i].a;
		scanf("%lf %lf", &e[i+m].r, &e[i+m].c);
	}
	if(bellman_ford()) 
		printf("YES\n");
	else 
		printf("NO\n");
	return 0;
}