Branched Evolution

Competitive Programming in Python

グラフ

AOJ DPL_2_B 中国人郵便配達問題

重み付き無向グラフで、すべての辺を通る閉路のうち最短経路の距離を求める。

ABC 187 F - Close Group

無向グラフについて、頂点を共有しない完全部分グラフの最小個数を求める。

ABC 187 E - Through Path

各頂点に整数が書かれた木に対して、クエリを処理していく。各クエリでは辺$(a,b)$と整数$x$が与えられ、$a$から$b$を通らずに到達できるすべての頂点に$x$を足し、最終的に各頂点に書かれた整数を答える。

Ford-Fulkerson 法

フローネットワークの最大流を求めるアルゴリズムとして知られるFord-Fulkerson法の実装を理解するのに苦労したので、できるだけ処理の過程がわかりやすいような実装を試みる。

ABC 180 E - Traveling Salesman among Aerial Cities

いわゆる巡回セールスマン問題.$n$ 個の点の間に移動コストが定められていて,点 $0$ から出発し,すべての点を通って点 $0$ に戻ってくるときの最小コストを求める.($n \leq 17$)

プレゼントの当選者を決定する問題を最小費用流で解く

問題 $ m $ 人の応募者と $n$ 個の商品があり、応募者 $i$ の商品 $j$ に対する希望度 $A _ {ij} \geq 0$ が定まっている。商品 $j$ は $L _ j > 0$ 個しかなく、$1$ 人の応募者に $2$ 個以上の商品が当選することはないとする。 また、希望度が $0$ の商品…