1.1 --- a/lemon/capacity_scaling.h	Sun Feb 21 18:55:30 2010 +0100
     1.2 +++ b/lemon/capacity_scaling.h	Fri Feb 26 14:00:20 2010 +0100
     1.3 @@ -139,9 +139,10 @@
     1.4      TEMPLATE_DIGRAPH_TYPEDEFS(GR);
     1.5  
     1.6      typedef std::vector<int> IntVector;
     1.7 -    typedef std::vector<char> BoolVector;
     1.8      typedef std::vector<Value> ValueVector;
     1.9      typedef std::vector<Cost> CostVector;
    1.10 +    typedef std::vector<char> BoolVector;
    1.11 +    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    1.12  
    1.13    private:
    1.14  
    1.15 @@ -798,15 +799,15 @@
    1.16        // Initialize delta value
    1.17        if (_factor > 1) {
    1.18          // With scaling
    1.19 -        Value max_sup = 0, max_dem = 0;
    1.20 -        for (int i = 0; i != _node_num; ++i) {
    1.21 +        Value max_sup = 0, max_dem = 0, max_cap = 0;
    1.22 +        for (int i = 0; i != _root; ++i) {
    1.23            Value ex = _excess[i];
    1.24            if ( ex > max_sup) max_sup =  ex;
    1.25            if (-ex > max_dem) max_dem = -ex;
    1.26 -        }
    1.27 -        Value max_cap = 0;
    1.28 -        for (int j = 0; j != _res_arc_num; ++j) {
    1.29 -          if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
    1.30 +          int last_out = _first_out[i+1] - 1;
    1.31 +          for (int j = _first_out[i]; j != last_out; ++j) {
    1.32 +            if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
    1.33 +          }
    1.34          }
    1.35          max_sup = std::min(std::min(max_sup, max_dem), max_cap);
    1.36          for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;