title: Hungarian Algorithm: finding minimum number of lines to cover zeroes?
body: <p>I am trying to implement the <a href="http://www.hungarianalgorithm.com/examplehungarianalgorithm.php" rel="noreferrer">Hungarian Algorithm</a> but I am stuck on the <a href="http://www.wikihow.com/Use-the-Hungarian-Algorithm" rel="noreferrer">step 5</a>. Basically, given a <code>n X n</code> matrix of numbers, how can I find minimum number of vertical+horizontal lines such that the zeroes in the matrix are covered?</p>
  
  <p><strong>Before someone marks this question as a duplicate of <a href="https://stackoverflow.com/questions/14795111/hungarian-algorithm-how-to-cover-0-elements-with-minimum-lines">this</a>, the solution mentioned there is incorrect and someone else <a href="https://stackoverflow.com/questions/19288464/minimum-lines-for-hungarian-algorithm">also ran into the bug in the code posted there</a></strong>. </p>
  
  <p>I am not looking for code but rather the concept by which I can draw these lines...</p>
  
  <p>EDIT:
  Please do not post the simple (but wrong) greedy algorithm:
  Given this input:</p>
  
  <pre><code>(0, 1, 0, 1, 1)
  (1, 1, 0, 1, 1)
  (1, 0, 0, 0, 1)
  (1, 1, 0, 1, 1)
  (1, 0, 0, 1, 0)
  </code></pre>
  
  <p>I select, column 2 obviously (0-indexed):</p>
  
  <pre><code>(0, 1, x, 1, 1)
  (1, 1, x, 1, 1)
  (1, 0, x, 0, 1)
  (1, 1, x, 1, 1)
  (1, 0, x, 1, 0)
  </code></pre>
  
  <p>Now I can either select row 2 or col 1 both of which have two "remaining" zeroes. If I select col2, I end up with incorrect solution down this path:</p>
  
  <pre><code>(0, x, x, 1, 1)
  (1, x, x, 1, 1)
  (1, x, x, 0, 1)
  (1, x, x, 1, 1)
  (1, x, x, 1, 0)
  </code></pre>
  
  <p>The correct solution is using 4 lines:</p>
  
  <pre><code>(x, x, x, x, x)
  (1, 1, x, 1, 1)
  (x, x, x, x, x)
  (1, 1, x, 1, 1)
  (x, x, x, x, x)
  </code></pre>