Bellman-Ford变形 Currency Exchange POJ

昊漫玉

　　题意：货币交换，有n种货币，m个货币兑换的地点，每一个地点提供两种货币的兑换且每一个地点的汇率不同，需要手续费，Rab(一单位货币a可以兑换货币b的数量）
　　现如今有货币s共有数量t,要求判断是否可以通过兑换使得货币s增加。如果图中有一个正权回路，可以通过这条回路不断增加某种货币的值，最后在增加货币s的值。
　　Bellman-Ford可以判断有没有负权回路。
　　建图，判断有没有正权回路。



//Bellman Flody判断有没有负边权
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 0x3f3f3f
using namespace std;
int n,m,s,g;
double t;
int u[300],v[300];
double r[300],c[300],d[105];
int Bellman()
{
memset(d,0,sizeof(d));
d=t;//d表示i种货币最多可以有d;
for(int i=1;i<=n;i++)
for(int j=1;j<g;j++)
{
if(d[v[j]]<(d[u[j]]-c[j])*r[j])
{
if(i==n) return 1;
d[v[j]]=(d[u[j]]-c[j])*r[j];
}
}
return 0;
}
int main()
{
cin>>n>>m>>s>>t;
g=1;
while(m--)
{
int x,y;
double r1,c1,r2,c2;
cin>>x>>y>>r1>>c1>>r2>>c2;
u[g]=x,v[g]=y,r[g]=r1,c[g]=c1;//从u到v的汇率
g++;
u[g]=y,v[g]=x,r[g]=r2,c[g]=c2;
g++;
}
if(Bellman()) printf("YES\n");
else printf("NO\n");
}