THE MATRIX PROBLEM (UVa Live Archive Asia - 2010 Harbin)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3095

問題

n*m行列が与えられる。行列の(i,j)の要素をcijと書いた時にL<=cij*ai/bj<=Uを満たすようなai,bjの列は存在するか？
1<=N,M<=400
1<=L<=U<=10000
1<=cij<=1000

解法

制約をlogを取って書き下すと
$b_j\le a_i + \log(c_{ij}) - \log L$
$a_i\le b_j + \log U - \log(c_{ij})$
となる。この大小関係の制約をすべて満たすai,bjが存在するかどうかは、グラフを作って負の閉路が存在するかどうかと等価である。なのでベルマンフォードを使って負閉路が存在するかどうかを調べば良い。TLEが厳しいのでループを(n+m)/10+10回で打ち切ったら通った。