/// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding

   /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum

   /// the maximum flow value and \ref NetworkSimplex algorithm for

   /// flow value and \ref NetworkSimplex for finding a minimum cost

   /// finding a minimum cost flow of that value.

   /// flow of that value.

   /// According to our benchmark tests \ref Preflow is generally the

   /// most efficient algorithm for the maximum flow problem and

   /// \ref NetworkSimplex is the most efficient for the minimum cost

   /// flow problem in LEMON.

   /// \param Graph The directed graph type the algorithm runs on.

   /// \tparam Graph The directed graph type the algorithm runs on.

   /// \param CapacityMap The type of the capacity (upper bound) map.

   /// \tparam CapacityMap The type of the capacity (upper bound) map.

   /// \param CostMap The type of the cost (length) map.

   /// \tparam CostMap The type of the cost (length) map.

   /// - Edge capacities and costs should be non-negative integers.

   /// - Edge capacities and costs should be \e non-negative \e integers.

   ///   However \c CostMap::Value should be signed type.

   ///   However \c CostMap::Value must be signed type.

   /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.

     typedef typename Graph::template NodeMap<Capacity> SupplyMap;

     typedef typename Graph::template NodeMap<Cost> SupplyMap;

     typedef Preflow<Graph, CapacityMap> MaxFlowImpl;

                             CostMap, SupplyMap >

                             CostMap, SupplyMap > MinCostFlowImpl;

       MinCostFlowImpl;

     /// The directed graph the algorithm runs on.

     // The directed graph the algorithm runs on

     const Graph &graph;

     const Graph &_graph;

     /// The modified capacity map.

     // The modified capacity map

     const CapacityMap &capacity;

     const CapacityMap &_capacity;

     /// The cost map.

     // The cost map

     const CostMap &cost;

     const CostMap &_cost;

     /// The edge map of the found flow.

     FlowMap flow;

     /// The source node.

     Node source;

     /// The target node.

     Node target;

     typedef Preflow<Graph, CapacityMap> MaxFlowImpl;

     // Edge map of the found flow

     /// \brief \ref Preflow class for finding the maximum flow value.

     FlowMap _flow;

     MaxFlowImpl preflow;

     // Node map of the found potentials

     PotentialMap _potential;

     // The source node

     Node _source;

     // The target node

     Node _target;

     MinCostMaxFlow( const Graph &_graph,

     MinCostMaxFlow( const Graph &graph,

                     const CapacityMap &_capacity,

                     const CapacityMap &capacity,

                     const CostMap &_cost,

                     const CostMap &cost,

                     Node _s, Node _t ) :

                     Node s, Node t ) :

       graph(_graph), capacity(_capacity), cost(_cost),

       _graph(graph), _capacity(capacity), _cost(cost), _flow(graph),

       source(_s), target(_t), flow(_graph),

       _potential(graph), _source(s), _target(t)

       preflow(_graph, _capacity, _s, _t)

     /// \brief Returns a const reference to the flow map.

     /// \brief Runs the algorithm.

     /// Returns a const reference to the flow map.

     /// Runs the algorithm.

     void run() {

       MaxFlowImpl preflow(_graph, _capacity, _source, _target);

       preflow.flowMap(_flow).runMinCut();

       MinCostFlowImpl mcf( _graph, _capacity, _cost,

                            _source, _target, preflow.flowValue() );

       mcf.run();

       _flow = mcf.flowMap();

       _potential = mcf.potentialMap();

     }

     /// \brief Returns a const reference to the edge map storing the

     /// found flow.

     ///

     /// Returns a const reference to the edge map storing the found flow.

       return flow;

       return _flow_result;

     }

     /// \brief Returns a const reference to the node map storing the

     /// found potentials (the dual solution).

     ///

     /// Returns a const reference to the node map storing the found

     /// potentials (the dual solution).

     ///

     /// \pre \ref run() must be called before using this function.

     const PotentialMap& potentialMap() const {

       return _potential_result;

         c += flow[e] * cost[e];

         c += _flow[e] * _cost[e];