Flow

AtCoder Regular Contest 080F: Prime Flip

http://arc080.contest.atcoder.jp/tasks/arc080_dまず列の差をとって区間の問題を距離が奇素数の2点を反転させてすべて0にする問題に帰着させる。座標i,jにある1を対応させるときのコストは |i-j|が奇素数→1 |i-j|が偶数→2 |i-j|が奇素数ではない奇数→3 と…

POJ 3422: Kaka's Matrix Travels

http://poj.org/problem?id=3422http://hos.ac/slides/20150319_flow.pdf ここのp69に載っている問題と同じ。負辺があるが、グラフが特殊な形をしているので、dijkstraで求めても最短経路が求まり、ポテンシャルも正しく求まる。これではつまらないので負辺…

POJ 3155: Hard Life

http://poj.org/problem?id=3155良問だと思う。hardness factorがkの時実現可能か考える。 辺と点を対応させた二部グラフを作る。 辺からそれが含む点に対して辺をはる。 そして辺にコスト1,点にコスト-kをつけると、Maximum Closure Problemに帰着できるの…

AOJ 2251: Merry Christmas

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

POJ 2226: Muddy Fields

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…

POJ 2724: Purifying Machine

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

POJ 3692: Kindergarten

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

POJ 1466: Girls and Boys

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

POJ 1486: Sorting Slides

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

POJ 2112: Optimal Milking

にぶたんして最大流流す。にぶたんの初期値を小さくしすぎて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>…

POJ 2987: Firing

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

AtCoder Regular Contest 074: Lotus Leaves

http://arc074.contest.atcoder.jp/tasks/arc074_dflow。行と列を代表する頂点を用意してうまく辺を張ると、辺の本数がO(H*W)になって十分高速。 int H, W; string S[MAX_N]; void solve() { cin >> H >> W; int s, t; rep(i, 0, H) { cin >> S[i]; rep(j, 0…

AtCoder Regular Contest 076F: Exhausted?

http://arc076.contest.atcoder.jp/tasks/arc076_d flowのお勉強。Hallの結婚定理より、人の集合Xの誰かが座れる椅子の集合をP(X)と置けば必要な椅子の数はX-P(X)である。椅子の集合は[0,L]or[R,M+1]と表せるのでそこに含まれる最大の人の数を求めればよい。…