最大流問題
最大流を流す練習問題 問題へのリンク 問題概要 人の人 がいる。ある人からある人には魔法パワーを渡していくことができる。具体的には、 組について 人 から人 に対して、最大で だけ魔法パワーを渡せる () ということが指定される。また、 人のうち、 人 …
最大流アルゴリズムを実装したときの verify に 問題へのリンク 問題概要 頂点数 、辺数 のフローネットワークが与えられる。 番目の辺は頂点 から頂点 へ張られていて、容量は である。 頂点 を始点、頂点 を終点とした最大流値を求めよ。 制約 考えたこと …
広く捉えれば「各スロットに対して止める秒数を割り当てる」方法を考える割当問題だと言えそう。 問題へのリンク 問題概要 のグリッド が与えられる。各マスには 0 から 9 までの数字が描かれている。 今、次の条件を満たす 0 以上の整数値 を考えたとき、 …
グリッドを市松模様に塗って、「黒色マス」と「白色マス」で二部マッチングするという、超典型問題! 問題へのリンク 問題概要 のグリッドが与えられます。 各マスは「障害物」が置かれているか、「空」であるかのいずれかです。入力データにおいては、障害…
opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。 競プロで言うところの「燃やす埋める」 問題へのリンク 問題概要 のグリッドがあって、各マス には整数…
最小費用の最大流を流すネットワークフロー問題! 問題へのリンク editorial 問題概要 個の駅があり、 と番号づけられている。 駅 と駅 の間には 種類の電車が走っていて、 番目の電車は 駅 を時刻 に出発して、 駅 に時刻 に到着し、 料金は である。 今、 …