how to use Network Flow to solve this?

Question

suppose we have a binary matrix (only zero or one elements).Adjacent elements of a given element is all 4 elements above,below,on the left and on the right of that element(if they exist). inversion is a pair which its numbers are different and also are adjacent.cost of a matrix is b*q where b is a natural number and q is number of inversions. we can flip any element by cost of a. so we want to minimize x*a + q*b where x is the number of flipped elements.

I think I can consider all elements as nodes and a source which is connected to all zero elements and a sink which is connected to all one elements. But I can find a good way to define edges between nodes and define their capacity till the answer of Network Flow problem be the answer of the original problem

Answer 1

Using Mathematica documentation (you can use pseudo code if you want):

To find maximum flow in a graph

• http://reference.wolfram.com/language/ref/FindMaximumFlow.html

To minimize xa+qb

• http://reference.wolfram.com/language/ref/LinearProgramming.html
• http://reference.wolfram.com/language/ref/FindMinimum.html
• http://reference.wolfram.com/language/ref/Minimize.html

To define edges between nodes and define their capacity

• http://reference.wolfram.com/language/ref/AdjacencyMatrix.html
• http://reference.wolfram.com/language/ref/AdjacencyGraph.html