# Minimum Cost Flow

Authors: Siyong Huang, Benjamin Qi

### Prerequisites

- Platinum - Maximum Flow

Triangle Inequality, Johnson's Algorithm, and Min Cost Flow

In this section I will briefly walk over my understanding of min cost flow. I would highly recommend reading through CP-Algorithm's Min Cost Flow to understand the solution idea first. Additionally, check the TopCoder tutorial for a more detailed explanation.

## Triangle Inequality

In graph theory, the **Triangle Inequality** states that if there is an edge $u \rightarrow v$ with weight $w$, and $d_k$ be the shortest path to node $k$ (for some reasonable definition of shortest path), then $d_v - d_u \leq w$.

Resources | |||
---|---|---|---|

Wikipedia | Mainly in geometry, but it has the gist of the idea. |

## Johnson's Algorithm

The main idea of **Johnson's Algorithm** is that if all edge weights are positive, then running Dijkstra's from each node would result in a $\mathcal{O}(VE \log E)$ algorithm. If there are any negative edges, **Johnson's Algorithm** defines a potential function $\pi$, such that for every edge $u,v,w$, the following holds: $w>=\pi(u)-\pi(v)$. Then, each edge weight can be transformed into $w \rightarrow w + \pi(v)-\pi(u)$, resulting in positive weight. This condition coincides with the **Triangle Inequality**, so we can arbitrarily pick a node and run a $\mathcal{O}(VE)$ shortest path algorithm to determine this function.

Resources | |||
---|---|---|---|

GFG | |||

Wikipedia |

## Minimum Cost Flow

The general idea of Min Cost Flow is to repeatedly push flow along the shortest path. Since flow graphs have negative edges, each step naively would take $\mathcal{O}(VE)$ time. To speed it up, we can use the same potential function from **Johnson's Algorithm** to employ Dijkstra for this process. In this case we *must* use distance from $S$, the source node, as the $\pi$ function. At each step, run Dijkstra's using the $\pi$ function, update the $\pi$ function to match the current distances, and then push flow along the shortest path, reversing edges as needed. Once flow is met or the sink is unreachable, terminate.

### Important Clarification

Note that the $\pi$ function stores values *before* the edge reverses happen. Luckily the **triangle inequality**'s equality case is along the shortest path, meaning that in a flow network it holds both forwards and backwards along edges in the shortest path. This means that although the $\pi$ function does not store the shortest paths, it still satisfies the **triangle inequality** for all edges.

$\pi(u)-\pi(v)=w \implies \pi(v)-\pi(u)=-w$

Resources | |||
---|---|---|---|

CP-Algorithms | Note: Does not use optimal solution, but explains the concept well. | ||

TopCoder |

## Implementation

With all this being said, here is my implementation.

template<int MN, int MM>struct MCF//MN = nodes, MM = edges [assume edges one-directional]{public:int N, M, S, T;int flow[MM*2], cap[MM*2], hd[MN], nx[MM*2], to[MM*2], cost[MM*2];int pi[MN], p[MN], d[MN];int vis[MN];void init(int n, int s, int t){

Also check out Benq's Implementation and KACTL's Implementation (which are a lot better than mine).

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|

CF | Normal | ## Show TagsMCF | Check CF | |||

CF | Normal | ## Show TagsMCF | Check CF | |||

CF | Normal | Check CF | ||||

CF | Hard | External Sol | ||||

CF | Very Hard | Check CF | ||||

CF | Very Hard |

## Applications

### Assignment Problem

### This section is not complete.

Better resources? I honestly just found some that came up in a google search.

Resources | |||
---|---|---|---|

Wikipedia | |||

YouTube - Algorithms Thread | |||

Topcoder |

### This section is not complete.

### Module Progress:

### Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

## Give Us Feedback on Minimum Cost Flow!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.