http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251DAGの最小パス被覆問題。パスで点を覆う際の最小本数を求める。まず二部グラフG(V,V';E)においてDAGでvからv'に辺がある時v∈V,v'∈V'に辺を張る。 すると答えは|V|-|最大マッチング|となる。有…

http://poj.org/problem?id=2226なるべく長い板を置いていく。 あとは板の縦方向の置き方と横方向の置き方を点に、草を辺に対応させて二部グラフを作り、最小点カバーを求めれば良い。 int H, W; int N, M; char F[60][60]; int X[60][60]; int Y[60][60]; i…

http://poj.org/problem?id=2724omochan.hatenablog.com ↑これとほとんど同じ。 一気に*を使って消せるやつ同士に辺を張ったグラフは2部グラフとなる。 2部グラフになるためには任意のサイクルの大きさが偶数であればよいが、Nコのbitのうち1つ変えるという…