Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

smax's blog

By smax, 18 months ago, In English

You can also read this on my blog: https://mzhang2021.github.io/cp-blog/simulating-cost-flow/

Thanks to gabrielwu for proofreading.


This post assumes knowledge of min/max cost flow and a rough understanding of the high-level methods for solving (successive shortest path and cycle canceling). Knowledge of specific algorithms and implementation details are not expected. Also solutions to some problems will use Aliens trick.


The cost flow problem is a well-known problem in literature that a whole slew of competitive programming problems can be formulated as. Unfortunately, competitive programming problems typically have constraints set too high for directly running even the most state of the art cost flow algorithm. However, in certain problems the flow network will have a very specific setup that allows us to figure out greedily the optimal flow (i.e. proving greedy with flow) or "simulate" the flow algorithm faster with data structures. That is what this post will be about.

I will say that I do not claim novelty over these ideas. This idea is (unsurprisingly) well-known in China. This particular post and some of the example problems are taken from this Chinese blog.

I will also describe everything below in terms of min cost flow, max cost is of course analogous. When describing flow network constructions, I will shorthand with (cost,capacity) for describing edges.

High-level Methods for Cost Flow

Most cost flow algorithms fall into one of these categories of high-level approaches. The two in particular that we will look at are:

  1. Successive Shortest Path: Repeatedly find a min cost augmenting path (a path with minimum total cost where all edges can still contain more flow) from source to sink and send flow through that path.
  2. Cycle Cancelling: Repeatedly find a negative cost cycle (a cycle with negative total cost where all edges can still contain more flow) and send flow through that cycle.

Note that in the cycle cancelling paradigm, there is no concept of source and sink, but you can solve for source and sink by adding an edge from sink to source with cost of and capacity of k for the min cost k-flow (or capacity if you want min cost max flow).

Min Cost Flow is Convex

Min cost flow as a function of amount of flow is convex. This makes intuitive sense, as you can always rearrange the augmenting paths you choose to pick less steep ones (lower cost) before more steep ones (higher cost). This fact is useful as it allows us to use Aliens trick.

Codeforces 802O: April Fools' Problem

Statement Summary: You are preparing and printing k problems for a contest over the course of n days. On the ith day, you can prepare a problem for cost ai and print a problem for cost bi. You must prepare a problem before printing it. In other words, if you prepare a problem on day i, you can only print it on some day ji. You can prepare and print at most one problem per day. What is the minimum cost of preparing and printing k problems?

Constraints: 1kn5105,1ai,bi109


Let's first think about solving this with flows. One straightforward way is to create 2n+2 nodes: a source s and sink t, plus nodes representing ai and bi for each i. We add the following edges:

  • s to each ai node with (ai,1)
  • each bi node to t with (bi,1)
  • each ai node to bj node where ij with (0,1)

The answer is the min cost k-flow of this network.

Image 1

Example for n=3

Now let's try to optimize using one of two methods. Both are possible and lead to different solutions for this problem.

Successive Shortest Path

This is the method described in the official editorial.

First, let's simplify this network to not use Ω(n2) edges. Consider a slightly different setup with n+2 nodes: a source s and sink t, plus nodes 1 through n. We add the following edges:

  • s to each i with (ai,1)
  • each i to t with (bi,1)
  • i to i+1 with (0,)

I claim the answer is also the min cost k-flow of this network. Essentially, a matching consists of picking some ai, waiting zero or more days (represent by taking some number of ii+1 edges), and then pick some bj where ij.

Image 2

Example for n=4

An augmenting path consists of sending flow from s to some i, then from i to j, and finally from j to t.

  • si and jt must of course have no flow going through them.
  • If ij, this is ok. We add +1 flow to each edge on the path from i to j.
  • If i>j, then we are sending flow along a reverse edge and cancelling out existing flow, so every edge on the path from i to j must have at least 1 flow, and the augmenting path adds 1 flow to each path edge.

And in the successive shortest path algorithm, we simply need to choose the augmenting path with minimum cost each time. So we need to choose a pair of indices i,j with minimum ai+bj, and either ij or there exists flow on every edge on the path between i and j.

So we need to be able to add +1 or 1 to a range and recompute the minimum cost valid (i,j) pair. This sounds like a job for lazy segment tree! We just repeat k times of querying the segtree for (i,j) and either add +1 or 1 to all edges in between i and j, giving us an O(klogn) solution.

The details for determining the minimum cost valid (i,j) pair are quite tedious, but the TLDR is that you have to store first and second minimums of the amount of flow through any edge in a subarray. I have an old submission that implements this idea with a ton of variables in the segtree node. It can probably be reduced with more thought.

Cycle Cancelling

To drastically simplify our analysis, we will apply Aliens trick. Binary search on some reward c, so now there is no requirement of at least k problems anymore, but instead you get a reward of c for completing one problem. So preparing a problem on day i and printing on day j costs ai+bjc. So there is an edge from t to s with (c,). We binary search for the minimum c that we complete at least k problems. This is valid because we know min cost flow is convex with respect to the amount of flow.

Now consider incrementally adding in nodes in decreasing order (from n to 1) and consider how the optimal flow changes after each additional node. When we add node i, we add edges sai, bit, and aibj for all ij. Upon adding node i, we consider the possibilities for how a new negative cycle could form.

  1. saibjts with cost ai+bjc. This is essentially matching ai with some unmatched bj.
  2. saibjaks with cost aiak. This is cancelling out some existing flow passing through sakbj and is equivalent to changing the matching to match bj with ai instead of ak.

Image 3 Image 4

Examples of negative cycles of the first and second types

Those are actually the only two cases we need to consider. For example, you might think we need to consider some cycle of the form saibjtbkals. This cycle would represent taking some matched pair (ai,bj) instead of (al,bk). However, if (al,bk) was originally matched in the first place, that would imply al+bkc, as otherwise tbjaist would be a negative cycle with weight calbk and we would have had to handle that before adding node i. And if saibjtbkals was a negative cycle, that would imply ai+bj<al+bk and therefore ai+bj<c, so we could instead take the negative cycle saibjts. In fact, we would ultimately converge to that state regardless, because if we took saibjtbkals first, then salbkts would form a negative cycle afterwards, so the end result after resolving all negative cycles is identical.

You can also confirm that after taking a negative cycle of one of the two types listed above (whichever one is more negative), we will not create any more additional negative cycles. So essentially, each time we add a node i to the network, we take at most one additional negative cycle.

Example: Can taking a type 2 cycle lead to creating a type 1 cycle?

Therefore, we can simply maintain a priority queue of potential negative cycles and iterate i from n to 1. When we match (ai,bj), we insert ai into the priority queue to allow for breaking up that matching and pairing bj with something else in the future. When we leave bi unmatched, we insert bic into the priority queue to allow for matching with that bi in the future. And at each step, if ai plus the minimum value in the priority queue is less than 0, then we take that option. The overall complexity is O(nlognlogA) (but with much better constant than the successive shortest path solution).

Code for Clarity

Notice that the final solution looks awfully similar to a greedy algorithm. And indeed, we can apply a greedy interpretation to this: each ai can be matched with some bj where ij for cost ai+bjc, and we want cost as negative as possible. Then the two types of negative cycles can be interpreted as "options" when introducing a new index i: either match ai with some unmatched bj or swap it with some existing (ak,bl) matching. In essence, the flow interpretation serves as a proof for the correctness of the greedy.

Do we need Aliens trick?

So with this first example, we can see two different solutions that arise from thinking about flows. The first one is probably impossible to think of without flows. For the second one, it might be difficult to prove Aliens trick can be applied here without formulating it as flow. Once Aliens trick is applied, the greedy is relatively easier to come up without thinking about flows, but having the flow network still gives us confidence in its correctness.

Codeforces 866D: Buy Low Sell High

Statement Summary: You have knowledge of the price of a stock over the next n days. On the ith day it will have price pi. On each day you can either buy one share of the stock, sell one existing share you currently have, or do nothing. You cannot sell shares you do not have. What is the maximum possible profit you can earn?

Constraints: 2n3105,1pi106


This problem has several interpretations that lead to the same code. You can think of it as slope trick. Or as greedy. Let's think about it as flows.

Firstly, we can loosen the restrictions by allowing for both buying and selling a stock on a given day. This won't change the answer since both buying and selling on the same day is equivalent to doing nothing.

Now we design the following flow network with n+2 nodes: a source s and sink t and n nodes representing days 1 through n. We add the following edges:

  • s to i for all 1in with (pi,1)
  • i to t for all 1in with (pi,1)
  • i to i+1 for all 1i<n with (0,)

The answer is thus the max cost flow of this network.

Image 5

Example for n=3

Now consider the cycle cancelling method. Add an edge from t to s with (0,). We are using a cost of 0 instead of because we do not require the max amount of flow, and forcing the max flow is not always optimal.

This network is extremely similar to the previous problem. We add the nodes from n to 1. When we add node i, the possible positive (since we are doing max cost flow) cycles are:

  • sijts for ij with cost pjpi
  • sijs for ij also with cost pjpi

So the code ends up being quite simple and may resemble some other greedy code you've seen.

Code

CSES Programmers and Artists

Statement Summary: You have n people, the ith person has xi amount of programming skill and yi amount of art skill. Each person can be assigned to be a programmer, artist, or neither. You need exactly a programmers and b artists. What is the maximum sum of skills attainable by some matching?

Constraints: 1n2105,a+bn,1xi,yi109


You get the drill now. Let's model this problem as a flow network. Here is one possible construction using n+4 nodes.

  • s to i with (0,1)
  • i to prog with (xi,1)
  • i to art with (yi,1)
  • prog to t with (0,a)
  • art to t with (0,b)

The answer is the max cost max flow of this network. Notice that in this case the maximum flow is also optimal as all augmenting paths will have positive weight.

Image 6

Example for n=3

Let's try approaching this with successive shortest path! Essentially, we repeatedly find an augmenting path from s to t with maximum cost and send 1 unit of flow through. After some pondering, we conclude we only have 4 types of paths to consider.

  • siprogt with cost xi
  • siartt with cost yi
  • siprogjartt with cost xixj+yj
  • siartjprogt with cost yiyj+xj

The first and fourth types of paths decrease the capacity of progt by 1, and the second and third types of paths decrease the capacity of artt by 1.

Do we need to consider any more complicated paths? Such as siprogjartkprogt? Turns out we don't. Suppose path siprogjartkprogt has the maximum cost. The cost is xixj+yjyk+xk. Now consider a different augmenting path that would also be valid, siprogt with cost xi. The fact that the other path was chosen implies xixj+yjyk+xk>xi, or yjxj+xkyk>0. This implies that there exists a positive cycle jartkprogj before introducing our new augmenting path, contradicting the property of successive shortest paths which ensures optimal cost flow with each new augmenting path added.

Therefore, we just need to maintain some heaps to repeatedly find the maximum cost path out of those 4 options:

  • pair unmatched i to programmer
  • pair unmatched i to artist
  • pair unmatched i to programmer, and switch some existing programmer j to artist
  • pair unmatched i to artist, and switch some existing artist j to programmer

My code is a bit verbose but attempts to implement this idea as straightforwardly as possible:

Code

More Problems

  • Vote: I like it
  • +293
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Great explanation! Can you make a post on Aliens trick next?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Thanks! To be honest, I only have a hand-wavy notion of how Aliens trick works. Here's my layman/non-rigorous explanation of it:

    Suppose you are trying to pick k things with minimum total cost (could be computed as sum of individual costs of these things, or something more complicated). Let f(x) denote the optimal minimum total achievable if you pick exactly x things. If f(x) is convex or concave, then you can instead binary search on some constant c and reframe it as having no limit on the number of things you can pick, but instead picking one thing yields c reward. And there exists some constant c such that the optimal solution picks k things. Usually after removing the limit of taking at most k things, the problem is easier to solve (e.g. with some greedy).

    For a deeper understanding of how/why this works, you can refer to the post I linked at the top, or there's also adamant's blog (which also contains an explanation for another simulating cost flow problem he commented below).

»
18 months ago, # |
  Vote: I like it +44 Vote: I do not like it

102331H - Honorable Mention is another example of a problem, which reduces to maxcost k-flow in a flow network:

After which it is solvable with Aliens trick. I have a more detailed explanation of its solution in my aliens trick tutorial.

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Great explanation! smax orz

In addition, could you tell us how to solve Cow At Large(Platinum Version)?

»
18 months ago, # |
  Vote: I like it +5 Vote: I do not like it

smax :orz:

Best blog read so far in my whole entire career of blog reading!

»
18 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Dear Smax,

I wanted to take a moment to express my sincere gratitude for the incredible explanation you provided. Your insightful words not only clarified the concept I was struggling with but also gave me a deeper understanding of the subject matter. Your expertise and ability to communicate complex ideas in a clear and concise manner are truly commendable.

I am genuinely thankful for the time and effort you put into crafting such a well-written explanation. Your dedication to helping others learn and grow is truly inspiring. Your contribution has made a significant impact on my understanding, and I feel more confident and knowledgeable as a result.

Once again, thank you for your exceptional explanation. Your kindness, expertise, and generosity in sharing your knowledge have made a lasting impression on me. I am truly grateful for your help and feel fortunate to have crossed paths with someone as knowledgeable and helpful as you.

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Very interesting blog! Can this be used to solve Codeforces 724E: Goods transportation?

  • »
    »
    18 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    The problem you linked technically doesn't pertain to this exact blog, since it's normal max flow instead of cost flow, but the same overarching principle applies: build the flow network, then instead of running template flow algorithm on this network, analyze the structure of the particular network to arrive at a faster solution.

»
18 months ago, # |
  Vote: I like it +58 Vote: I do not like it

is your name pronounced "smacks" or "ess — macks"

»
18 months ago, # |
  Vote: I like it +15 Vote: I do not like it

maxflow? more like: smaxflow

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey smax, is this problem solvable by this method. I am unable to map it into a flow problem.