title: Minimum Mean Weight Cycle - Intuitive Explanation
body: <p>In a directed graph, we are looking for the cycle that had the lowest average edge weights. For instance, a graph with nodes 1 and 2 with path from 1 to 2 of length 2 and from 2 to 1 of length 4 would have minimum mean cycle of 3.</p>
  
  <p>Not looking for a complicated method(Karp), but a simple backtracking wtih pruning solution. An explanation is given as "Solvable with backtracking with important pruning when current running mean is greater than the best found mean weight cycle cost."</p>
  
  <p>However, why does this method work? If we are halfway through a cycle and the weight is more than the best found mean, isn't it possible that with small weight edges we can reach a situation where our current cycle can go lower than the best found mean?</p>
  
  <p>Edit: Here is a sample problem: <a href="http://uva.onlinejudge.org/index.php?option=onlinejudge&amp;page=show_problem&amp;problem=2031" rel="nofollow">http://uva.onlinejudge.org/index.php?option=onlinejudge&amp;page=show_problem&amp;problem=2031</a></p>