| bool | MIN_COST_FLOW(graph& G, edge_array<int> lcap, edge_array<int> ucap, edge_array<int> cost, node_array<int> supply, edge_array<int>& flow) | |
| MIN_COST_FLOW takes as arguments a directed graph G(V, E), an edge_array lcap (ucap) giving for each edge a lower (upper) capacity bound, an edge_array cost specifying for each edge an integer cost and a node_array supply defining for each node v a supply or demand (if supply[v] < 0). If a feasible flow (fulfilling the capacity and mass balance conditions) exists it computes such a flow of minimal cost and returns true, otherwise false is returned. The algorithm is based on capacity scaling and successive shortest path computation (cf. [25] and [4]) and has running time O(| E| logU(| E| + | V| log| V|)). | ||
| bool | MIN_COST_FLOW(graph& G, edge_array<int> cap, edge_array<int> cost, node_array<int> supply, edge_array<int>& flow) | |
| This variant of MIN_COST_FLOW assumes that lcap[e] = 0 for every edge e in E. | ||
| int | MIN_COST_MAX_FLOW(graph& G, node s, node t, edge_array<int> cap, edge_array<int> cost, edge_array<int>& flow) | |
| MIN_COST_MAX_FLOW takes as arguments a directed graph G(V, E), a source
node s, a sink node t, an edge_array cap giving for each edge in G a
capacity, and an edge_array cost specifying for each edge an integer cost.
It computes for every edge e in G a flow flow[e] such that the total
flow from s to t is maximal, the total cost of the flow is minimal,
and
0 < = flow[e] < = cap[e] for all edges e.
MIN_COST_MAX_FLOW returns the total flow from s to t.
|
||