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つ変えるという…

http://poj.org/problem?id=3692男女がお互いを知っている最大の集合を求める。 これは男女がお互いを知らない、ということはない最大の集合であるので、 知り合いではない男女を辺でつないで最大安定集合を求めれば良い。 あとは|最大安定集合|=V-|最大マッ…

http://poj.org/problem?id=1466最大安定集合を求める。 二部グラフになるので|最小点カバー|=|最大マッチング|、 任意のグラフについて|最小点カバー|+|最大安定集合|=|V|よりできる。 頂点を2倍にしてあげると実装が楽。 簡単な証明いろいろ。 |最大マッチ…

http://poj.org/problem?id=1486完全マッチングに必ず使われる辺を答えればよい。 それはフローが流れた辺を削除したとき完全マッチングになるかどうかで判断すればよい。その際に押し戻すテクを使ってN-1のフローを作り、対象の辺の容量を0にしてdfsすると…

にぶたんして最大流流す。にぶたんの初期値を小さくしすぎてWA出した… struct edge {int to, cap, rev; }; vector<edge> G[MAX_N]; bool used[MAX_N]; void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].</edge>…

http://poj.org/problem?id=2914これもフローとはまた違った話。全域最小カット。Stoer–Wagnerを使う。Stoer–Wagnerは 「点の集合からの辺のコストの合計が大きいもの点から取っていって、最後から二番目に取った点sと最後に取った点tの最小カットは tから生…

Mengerの定理より全域最小点カットを求めれば良い。すべての点対に対してフローを流せばできるが、それではTLE。 全域最小辺カットならO(V^3)のアルゴリズム(Stoer-Wagner)が存在するが、全域最小点カットは見つけられなかった。全域最小点カットが2以上にな…

http://poj.org/problem?id=2987はじめてフローでまともな問題解いたかもしれない。maximum closure problemという有名問題。↓wiki参照。 https://en.wikipedia.org/wiki/Closure_problem何個使うかも答えなければいけないが、それはmin-cutを得る際の(cap>0…

3109 http://poj.org/problem?id=3109座標圧縮+平面走査segtree。実装ややこしいはずだけど一発で通って気持ちがいい。実装ちゃんと練ればすんなりいくんだね。3735 http://poj.org/problem?id=37351+B+B^2...の形が出てくるので行列の累乗和を貼って終了、…

2441 http://poj.org/problem?id=2441bitdpやるだけしたら3938MS/4000MSで超ギリギリだったw3254 http://poj.org/problem?id=3254sampleも一発で通って気持ちがいい。bitdp。3420 http://poj.org/problem?id=3420行列累乗。一行ごとのstateをbitで表して行列…

3185 http://poj.org/problem?id=3185普通に端から反転させるだけ…と思ったが、端の場合分けで反転の回数カウントしていなくてWA生やしまくった。1222 http://poj.org/problem?id=1222これも端を決めて反転するだけ。反転は決めることが本質。2100 http://po…