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,v;
double r,c,d;
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]<(d]-c)*r)
{
if(i==n) return 1;
d]=(d]-c)*r;
}
}
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=x,v=y,r=r1,c=c1;//从u到v的汇率
g++;
u=y,v=x,r=r2,c=c2;
g++;
}
if(Bellman()) printf("YES\n");
else printf("NO\n");
}
页:
[1]