Let us formalize the problem as the minimum cut problem.

First, we have a source \(S\) and a sink \(T\).

For each \(1 \leq i \leq N\), we have a path of length \(M\): \(S=V_{i,0} \to V_{i,1} \to \cdots \to V_{i,M}=T\). By spanning an edge \(V_{i,k} \to V_{i,k-1}\) with capacity \(\infty\) for each \(1 \leq k \leq M\), first some of \(V_{i,k}\) will side with \(S\) in the minimum cut, and the rest will side with \(T\).

Let us make it so that cutting between \(V_{i,k}\) and \(V_{i,k-1}\) corresponds to choosing \(A_{i,k}\). We can do this by spanning an edge \(V_{i,k-1} \to V_{i,k}\) with capacity \(C_{i,k}\) to express the cost of choosing \(A_{i,k}\).

Next, let us add edges that correspond to the cost \(|x_i-x_j| \times W_{i,j}\). We can rephrase this cost as follows.

• For each integer \(a\), the following cost is incurred.
  • \(W_{i,j}\), if \(x_i \leq a\) and \(a+1 \leq x_j\).
  • \(W_{i,j}\), if \(x_j \leq a\) and \(a+1 \leq x_i\).

The condition “\(x_i \leq a\) and \(a+1 \leq x_j\)” can be rephased as “\(V_{i,p}\) sides with \(T\) and \(V_{j,q}\) sides with \(S\) in the cut” using appropriate \(0 \leq p,q \leq M\). Thus, we can span an edge \(V_{j,q} \to V_{i,p}\) with capacity \(W_{i,j}\) to express the cost corresponds to this condition.

By putting together \(a\)’s that use the same \(p,q\), there will be \(O(M)\) edges to add for each pair \((i,j)\).

Now that our graph is ready, we just need to find its minimum cut = the maximum flow.

Since the graph has \(O(NM)\) vertices and \(O(N^2M)\) edges, Dinic’s algorithm solves the problem in \(O(N^4M^3)\) time.