Index: lemon/capacity_scaling.h
===================================================================
--- lemon/capacity_scaling.h	(revision 876)
+++ lemon/capacity_scaling.h	(revision 877)
@@ -134,5 +134,5 @@
 
     typedef std::vector<int> IntVector;
-    typedef std::vector<bool> BoolVector;
+    typedef std::vector<char> BoolVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
@@ -197,4 +197,5 @@
 
       int _node_num;
+      bool _geq;
       const IntVector &_first_out;
       const IntVector &_target;
@@ -211,8 +212,8 @@
 
       ResidualDijkstra(CapacityScaling& cs) :
-        _node_num(cs._node_num), _first_out(cs._first_out), 
-        _target(cs._target), _cost(cs._cost), _res_cap(cs._res_cap),
-        _excess(cs._excess), _pi(cs._pi), _pred(cs._pred),
-        _dist(cs._node_num)
+        _node_num(cs._node_num), _geq(cs._sum_supply < 0),
+        _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
+        _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
+        _pred(cs._pred), _dist(cs._node_num)
       {}
 
@@ -233,5 +234,6 @@
 
           // Traverse outgoing residual arcs
-          for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
+          int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
+          for (int a = _first_out[u]; a != last_out; ++a) {
             if (_res_cap[a] < delta) continue;
             v = _target[a];
@@ -688,5 +690,5 @@
       if (_sum_supply > 0) return INFEASIBLE;
       
-      // Initialize maps
+      // Initialize vectors
       for (int i = 0; i != _root; ++i) {
         _pi[i] = 0;
@@ -695,13 +697,16 @@
 
       // Remove non-zero lower bounds
+      const Value MAX = std::numeric_limits<Value>::max();
+      int last_out;
       if (_have_lower) {
         for (int i = 0; i != _root; ++i) {
-          for (int j = _first_out[i]; j != _first_out[i+1]; ++j) {
+          last_out = _first_out[i+1];
+          for (int j = _first_out[i]; j != last_out; ++j) {
             if (_forward[j]) {
               Value c = _lower[j];
               if (c >= 0) {
-                _res_cap[j] = _upper[j] < INF ? _upper[j] - c : INF;
+                _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF;
               } else {
-                _res_cap[j] = _upper[j] < INF + c ? _upper[j] - c : INF;
+                _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF;
               }
               _excess[i] -= c;
@@ -719,13 +724,14 @@
 
       // Handle negative costs
-      for (int u = 0; u != _root; ++u) {
-        for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
-          Value rc = _res_cap[a];
-          if (_cost[a] < 0 && rc > 0) {
-            if (rc == INF) return UNBOUNDED;
-            _excess[u] -= rc;
-            _excess[_target[a]] += rc;
-            _res_cap[a] = 0;
-            _res_cap[_reverse[a]] += rc;
+      for (int i = 0; i != _root; ++i) {
+        last_out = _first_out[i+1] - 1;
+        for (int j = _first_out[i]; j != last_out; ++j) {
+          Value rc = _res_cap[j];
+          if (_cost[j] < 0 && rc > 0) {
+            if (rc >= MAX) return UNBOUNDED;
+            _excess[i] -= rc;
+            _excess[_target[j]] += rc;
+            _res_cap[j] = 0;
+            _res_cap[_reverse[j]] += rc;
           }
         }
@@ -737,13 +743,9 @@
         _excess[_root] = -_sum_supply;
         for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
-          int u = _target[a];
-          if (_excess[u] < 0) {
-            _res_cap[a] = -_excess[u] + 1;
-          } else {
-            _res_cap[a] = 1;
-          }
-          _res_cap[_reverse[a]] = 0;
+          int ra = _reverse[a];
+          _res_cap[a] = -_sum_supply + 1;
+          _res_cap[ra] = 0;
           _cost[a] = 0;
-          _cost[_reverse[a]] = 0;
+          _cost[ra] = 0;
         }
       } else {
@@ -751,8 +753,9 @@
         _excess[_root] = 0;
         for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
+          int ra = _reverse[a];
           _res_cap[a] = 1;
-          _res_cap[_reverse[a]] = 0;
+          _res_cap[ra] = 0;
           _cost[a] = 0;
-          _cost[_reverse[a]] = 0;
+          _cost[ra] = 0;
         }
       }
@@ -763,6 +766,7 @@
         Value max_sup = 0, max_dem = 0;
         for (int i = 0; i != _node_num; ++i) {
-          if ( _excess[i] > max_sup) max_sup =  _excess[i];
-          if (-_excess[i] > max_dem) max_dem = -_excess[i];
+          Value ex = _excess[i];
+          if ( ex > max_sup) max_sup =  ex;
+          if (-ex > max_dem) max_dem = -ex;
         }
         Value max_cap = 0;
@@ -790,5 +794,6 @@
       // Handle non-zero lower bounds
       if (_have_lower) {
-        for (int j = 0; j != _res_arc_num - _node_num + 1; ++j) {
+        int limit = _first_out[_root];
+        for (int j = 0; j != limit; ++j) {
           if (!_forward[j]) _res_cap[j] += _lower[j];
         }
@@ -813,6 +818,9 @@
       while (true) {
         // Saturate all arcs not satisfying the optimality condition
+        int last_out;
         for (int u = 0; u != _node_num; ++u) {
-          for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
+          last_out = _sum_supply < 0 ?
+            _first_out[u+1] : _first_out[u+1] - 1;
+          for (int a = _first_out[u]; a != last_out; ++a) {
             int v = _target[a];
             Cost c = _cost[a] + _pi[u] - _pi[v];
@@ -831,6 +839,7 @@
         _deficit_nodes.clear();
         for (int u = 0; u != _node_num; ++u) {
-          if (_excess[u] >=  _delta) _excess_nodes.push_back(u);
-          if (_excess[u] <= -_delta) _deficit_nodes.push_back(u);
+          Value ex = _excess[u];
+          if (ex >=  _delta) _excess_nodes.push_back(u);
+          if (ex <= -_delta) _deficit_nodes.push_back(u);
         }
         int next_node = 0, next_def_node = 0;
Index: lemon/network_simplex.h
===================================================================
--- lemon/network_simplex.h	(revision 835)
+++ lemon/network_simplex.h	(revision 877)
@@ -165,5 +165,5 @@
 
     typedef std::vector<int> IntVector;
-    typedef std::vector<bool> BoolVector;
+    typedef std::vector<char> CharVector;
     typedef std::vector<Value> ValueVector;
     typedef std::vector<Cost> CostVector;
@@ -213,6 +213,6 @@
     IntVector _last_succ;
     IntVector _dirty_revs;
-    BoolVector _forward;
-    IntVector _state;
+    CharVector _forward;
+    CharVector _state;
     int _root;
 
@@ -222,4 +222,6 @@
     int stem, par_stem, new_stem;
     Value delta;
+    
+    const Value MAX;
 
   public:
@@ -243,5 +245,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -295,5 +297,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -334,5 +336,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -407,5 +409,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -510,5 +512,5 @@
       const IntVector  &_target;
       const CostVector &_cost;
-      const IntVector  &_state;
+      const CharVector &_state;
       const CostVector &_pi;
       int &_in_arc;
@@ -632,7 +634,7 @@
     NetworkSimplex(const GR& graph, bool arc_mixing = false) :
       _graph(graph), _node_id(graph), _arc_id(graph),
+      MAX(std::numeric_limits<Value>::max()),
       INF(std::numeric_limits<Value>::has_infinity ?
-          std::numeric_limits<Value>::infinity() :
-          std::numeric_limits<Value>::max())
+          std::numeric_limits<Value>::infinity() : MAX)
     {
       // Check the value types
@@ -1021,7 +1023,7 @@
           Value c = _lower[i];
           if (c >= 0) {
-            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
+            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
           } else {
-            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
+            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
           }
           _supply[_source[i]] -= c;
@@ -1215,5 +1217,5 @@
         e = _pred[u];
         d = _forward[u] ?
-          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
+          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
         if (d < delta) {
           delta = d;
@@ -1226,5 +1228,5 @@
         e = _pred[u];
         d = _forward[u] ? 
-          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
+          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
         if (d <= delta) {
           delta = d;
@@ -1425,5 +1427,5 @@
         findJoinNode();
         bool change = findLeavingArc();
-        if (delta >= INF) return UNBOUNDED;
+        if (delta >= MAX) return UNBOUNDED;
         changeFlow(change);
         if (change) {
