String Phone (UVa Live Archive Asia - 2010 Daejeon(Korea))

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=2850

問題

街の各ビルの四隅のどこかに警備員を立たせる。警備員同士は糸電話を使って連絡を取り合う。しかし糸電話は糸がピンと張っている状態でないと機能しない。警備員同士の糸電話の長さを与えるので全ての糸電話が機能するような警備員の配置はあるか？
ビルの数n<=3000
糸電話の数m<=300000

解法

2SATで解く。まず各警備員が(x+y)が奇数の位置か偶数の位置にいるかを2SATで決定する。もしその割当がその連結成分でできたら次は警備員をビルの左側に置くか右側に置くかを2SATで決定させる。計算量はたぶんO(n+m)。