Revert to long long int since currently I don't know a better solution.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_MIN_COST_FLOW_H
20 #define LEMON_MIN_COST_FLOW_H
22 /// \ingroup min_cost_flow
25 /// \brief An efficient algorithm for finding a minimum cost flow.
27 #include <lemon/network_simplex.h>
31 /// \addtogroup min_cost_flow
34 /// \brief An efficient algorithm for finding a minimum cost flow.
36 /// \ref MinCostFlow provides an efficient algorithm for finding
37 /// a minimum cost flow.
39 /// This class is just an alias for \ref NetworkSimplex,
40 /// which is the most efficient algorithm for the minimum cost
41 /// flow problem in LEMON according to our benchmark tests.
42 /// For the detailed documentation of this class see
43 /// \ref NetworkSimplex.
45 /// There are four implementations for the minimum cost flow problem,
46 /// which can be used exactly the same way.
47 /// - \ref CapacityScaling
48 /// - \ref CostScaling
49 /// - \ref CycleCanceling
50 /// - \ref NetworkSimplex
52 /// \tparam Graph The directed graph type the algorithm runs on.
53 /// \tparam LowerMap The type of the lower bound map.
54 /// \tparam CapacityMap The type of the capacity (upper bound) map.
55 /// \tparam CostMap The type of the cost (length) map.
56 /// \tparam SupplyMap The type of the supply map.
59 /// - Edge capacities and costs should be \e non-negative \e integers.
60 /// - Supply values should be \e signed \e integers.
61 /// - The value types of the maps should be convertible to each other.
62 /// - \c CostMap::Value must be signed type.
64 /// \author Peter Kovacs
66 template < typename Graph,
67 typename LowerMap = typename Graph::template EdgeMap<int>,
68 typename CapacityMap = typename Graph::template EdgeMap<int>,
69 typename CostMap = typename Graph::template EdgeMap<int>,
70 typename SupplyMap = typename Graph::template NodeMap<int> >
72 public NetworkSimplex< Graph, LowerMap, CapacityMap,
75 typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
76 CostMap, SupplyMap > MinCostFlowImpl;
77 typedef typename Graph::Node Node;
78 typedef typename SupplyMap::Value Supply;
82 /// General constructor (with lower bounds).
83 MinCostFlow( const Graph &graph,
84 const LowerMap &lower,
85 const CapacityMap &capacity,
87 const SupplyMap &supply ) :
88 MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
90 /// General constructor of the class (without lower bounds).
91 MinCostFlow( const Graph &graph,
92 const CapacityMap &capacity,
94 const SupplyMap &supply ) :
95 MinCostFlowImpl(graph, capacity, cost, supply) {}
97 /// Simple constructor (with lower bounds).
98 MinCostFlow( const Graph &graph,
99 const LowerMap &lower,
100 const CapacityMap &capacity,
103 Supply flow_value ) :
104 MinCostFlowImpl( graph, lower, capacity, cost,
105 s, t, flow_value ) {}
107 /// Simple constructor (without lower bounds).
108 MinCostFlow( const Graph &graph,
109 const CapacityMap &capacity,
112 Supply flow_value ) :
113 MinCostFlowImpl( graph, capacity, cost,
114 s, t, flow_value ) {}
116 }; //class MinCostFlow
122 #endif //LEMON_MIN_COST_FLOW_H