POJ 1860 Currency Exchange (BellmanFord)

题目大意：有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加。这道题能加深对Bellman-Ford的理解。才发现Bellman-Ford不止能求最短路，也能求一类“最优路”问题。和求最短路一样，给每个节点一个dist[]标号，这里表示该节点金币额的下界。然后就像最短路那样“松弛”：对于每条边(u,v)， dist[v] = max(dist[v], [dist[u]-commission(u,v)] * rate(u,v))；最后判断一下dist[s]是否比初始值大即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MID(x,y) ((x+y)>>1)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long LL;
//¾«¶ÈÄ£°å
const double eps = 1e-8;
bool dy(double x,double y)  {   return x > y + eps;} 		// x > y
bool xy(double x,double y)  {   return x < y - eps;} 		// x < y
bool dyd(double x,double y) {   return x > y - eps;} 		// x >= y
bool xyd(double x,double y) {   return x < y + eps;}     	// x <= y
bool dd(double x,double y)  {   return fabs( x - y ) < eps;}    // x == y

struct node{
    int u, v;
    double rate, commission;
}edge[201];
int n, m, s, k;
double v;
double dist[101];

bool bellman_ford(int s, double v){
    mem(dist, 0);
    dist[s] = (double)v;
    while(xyd(dist[s], v)){
        bool relax = false;
        for (int i = 0; i < k; i ++){
            if (xy(dist[edge[i].v], (dist[edge[i].u] - edge[i].commission)*edge[i].rate)){
                relax = true;
                dist[edge[i].v] = (dist[edge[i].u] - edge[i].commission)*edge[i].rate;
            }
        }
        if (!relax)
            break;
    }
    if (dy(dist[s], v))
        return true;
    return false;
}

int main(){
    scanf("%d %d %d %lf", &n, &m, &s, &v);
    k = 0;
    for (int i = 0; i < m; i ++){
        int tmpa, tmpb;
        double rab, cab, rba, cba;
        scanf("%d %d %lf %lf %lf %lf", &tmpa, &tmpb, &rab, &cab, &rba, &cba);
        edge[k].u = tmpa;
        edge[k].v = tmpb;
        edge[k].rate = rab;
        edge[k++].commission = cab;
        edge[k].u = tmpb;
        edge[k].v = tmpa;
        edge[k].rate = rba;
        edge[k++].commission = cba;
    }
    if (bellman_ford(s, v))
        puts("YES");
    else
        puts("NO");
	return 0;
}

举杯独醉，饮罢飞雪，茫然又一年岁。 ------AbandonZHANG