CurrencyExchange-bellman_ford

update@2011-09-12

//主要代码
#define eps 1e-8
struct node{
    int from,to;
    double c,r;//c是手续费 r是汇率
};
struct node edge[210];double d[101];//
double getW(double curr,const struct node &a){
    return (curr-a.c)*a.r;
}
int relax_method(int S,int N,double v,int count){
    memset(d,0,sizeof(d));d[S] = v;
    //d[i]也可以初始化为-INF, {i|1 <= i <= N and i != S}
    //因为-INF一定小于getW(d[edge[i].from],edge[i])不会影响到松弛操作
    while(!(d[S] - v > eps)){
        bool can_relax = false;
        for(int  i = 0;i <= count;i++){
            if(d[edge[i].to]+eps < getW(d[edge[i].from],edge[i])){
                //开始总觉得两种不同币种的值进行比较不对
                //可以这样想,由于考虑了每条边,所以只有两种情况,从
                //S出发可以回到S,回到S之后就是同种币种之间的比较
                //如果回不到S d[S]的值肯定是没有被改变的
                can_relax = true;
                d[edge[i].to] = getW(d[edge[i].from],edge[i]);
            }
        }
        if(can_relax == false) return d[S] > (v+eps);
    }
    return d[S] > (v+eps);
}
void toEdge(int count,int f,int t,double r,double c){
    edge[count].from = f;edge[count].to = t;
    edge[count].r    = r;edge[count].c  = c;
}


题目链接:Currency Exchange
水题,主要用到了bellman_ford中的松弛操作,不断松弛 直到不能松弛为止
开始没思路,看了解题报告就去套bellman_ford,这里边权不是固定值,边权可以看作兑换前后的差值,注意下退出循环的条件