POJ 1860 Currency Exchange Bellman-Ford
题意：能否通过套汇盈利。题解：
#include <iostream>
using namespace std;
double dist, v;
int n, m, s;
struct item
{
int a, b;
double r,c;
} node;
bool Bellman_ford ()
{
int i, j;
memset(dist,0,sizeof(dist));
dist = v;
for ( i = 1; i < n; i++ )
{
for ( j = 1; j <= m * 2; j++ )
if ( dist.b] < ( dist.a] - node.c ) * node.r )
dist.b] = ( dist.a] - node.c ) * node.r;
}
for ( j = 1; j <= m * 2; j++ )
if ( dist.b] < ( dist.a] - node.c ) * node.r )
return true;
return false;
}
int main()
{
int a, b;
double r1, r2, c1, c2;
cin >> n >> m >> s >> v;
for ( int i = 1; i <= m * 2; i++ )
{
cin >> a >> b >> r1 >> c1 >> r2 >> c2;
node.a = a;
node.b = b;
node.r = r1;
node.c = c1;
i++;
node.a = b;
node.b = a;
node.r = r2;
node.c = c2;
}
if ( Bellman_ford () )
cout << "YES" << endl;
else
cout << "NO" << endl;
return 0;
}
页:
[1]