https://colopl2018-final.contest.atcoder.jp/tasks/colopl2018_final_e rep(i, H + 1) rep(W, M) AS[i] += min(i, A[j]); 通した人の多くがこのようなコードを書いているわけですが、これだけ解説します。 Bがsource側、Aがsink側だとします。 Bのうちi辺…

https://colopl2018-final-open.contest.atcoder.jp/A オンサイトだとこれでも詰まるよねぇ…端が繋がる時注意。B スタックでO(N)。再帰やってTLEするの普段絶対やらないと思うし、怖いね。C 一次式にしてもよくわからなかったので分割統治でやった。これ解け…

https://community.topcoder.com/stat?c=round_overview&er=5&rd=16083Easy Kruskalやるだけなんだけど貼るの遅かった…もうちょっとちゃんと整備します。 struct ChristmasTreeDecoration { vector<int> col; vector<int> x; vector<int> y; int solve(vector<int> _col, vector<int> </int></int></int></int></int>…

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

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

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

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

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

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…

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