Skip to content

MINCOST

Why Practice This

This is the standard min-cost flow pattern with one extra responsibility: you must also reconstruct an explicit transportation plan on the original undirected edges.

Recognition Cue

Reach for min-cost flow when:

  • you must send an exact amount of flow
  • capacities and costs both matter
  • local greedy shipment choices are not obviously safe

The strongest smell is:

  • "send exactly k units with minimum total cost"

That is usually not pure max flow and not shortest paths alone. It is min-cost flow.

Problem-Specific Transformation

The transport story is rewritten as:

  • each road becomes residual-network edges with capacity and cost
  • the goal is no longer route planning by hand, but repeated cheapest augmenting paths

Then the extra judge requirement is layered on top:

  • after the optimal flow is found, recover the net direction on each original undirected road

So the task becomes:

  • standard min-cost flow core
  • plus one reconstruction step on original edges

Core Idea

Model each undirected road (u, v) with capacity d and cost c as two directed edges:

  • u -> v with capacity d, cost c
  • v -> u with capacity d, cost c

Then run successive shortest augmenting path with potentials:

  1. find the shortest path in reduced costs
  2. push as much flow as possible through that path
  3. update potentials
  4. repeat until k units are sent or no augmenting path exists

Because all costs are nonnegative, an optimal solution never needs positive flow in both directions on the same original road. So after the flow is finished, the net direction on each original edge is:

flow(u -> v) - flow(v -> u)

and that is exactly what we print.

Complexity

With n <= 100, the standard implementation is fast enough:

  • each augmentation uses Dijkstra on reduced costs
  • total complexity is easily acceptable for this constraint range

Pitfalls / Judge Notes

  • If fewer than k units can reach the sink, print only -1.
  • Use long long for distances and total cost.
  • Reconstruct the answer on the original undirected edges, not on residual edges.
  • The printed edge list can be any valid optimal transportation plan.

Reusable Pattern

  • Topic page: Maximum Flow
  • Practice ladder: Maximum Flow ladder
  • Starter template: min-cost-flow.cpp
  • Notebook refresher: Graph cheatsheet
  • Carry forward: separate the reusable residual-network machinery from the cost-specific shortest-path layer.
  • This note adds: the duplicate-edge handling and judge-specific modeling for this transport network.

Solutions

Judge Note

  • VN SPOJ hidden tests may contain duplicate undirected edges.
  • For the accepted version in mincost.cpp, only the last occurrence of each undirected pair is kept before building the flow network.
  • The min-cost flow model itself is still the standard one: each undirected road becomes two directed edges with the same capacity and cost.
  • The earlier WA came from treating repeated roads as separate parallel edges when this judge expects overwrite-by-last-input behavior.