問題文 http://poj.org/problem?id=24551~Nの頂点があって、1からNの間をT回移動したい。 一度移動に使った辺は使用できない。 移動の時に使う辺のコストの最大値を最小化せよ。 二分探索+最大流。 二分探索で、移動に使用する辺の最大値を決め打ちする。 決…

問題文 http://poj.org/problem?id=2391n頭の牛とm個のフィールドがある。 フィールドにはそれぞれ小屋があり、入れる牛の数も決まっている。 また、フィールド同士は辺でつながっている。 辺には牛が通れる数の制限はない。 全ての牛が小屋に入ることを考え…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5874.pdf 二部グラフのマッチング。嘘解法だった。本当は一般グラフのマッチングで解くらしい。 #include<iostream> #include<vector> #include<algorithm> #include<set> #define INF 1LL<<62 #define MAX_V 1000 using namespace std;</set></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/41/4130.pdf人の名前と要らないものと欲しいもののリストが与えられる。 物々交換により欲しいものを手に入れたい。 自分が持っているいらないものが相手の欲しいものであり、かつ 自分の欲しいものが相…

問題文 https://icpcarchive.ecs.baylor.edu/external/36/3673.pdfn×nの黒と白のグリッドが与えられる。任意の行と行、列と列をスワップすることができる。この操作を繰り返すことで、縦と横の番号が同じようなマスを全て白にできるか判定せよ。 斜めに並べ…

問題文 https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せ…

問題文 http://poj.org/problem?id=3692 最大クリーク問題。 二部グラフになっているので補グラフの最大独立集合を求める。 最大クリーク=補グラフの最大独立集合 が成り立つ。また二部グラフなら、 最大独立集合=頂点数-最大マッチング が成り立つ。 #inclu…

問題文 http://uva.onlinejudge.org/external/115/11506.htmlコンピュータを頂点、ケーブルを辺とした無向グラフが与えられる。 コンピュータとケーブルを破壊して番号1のコンピュータから 番号Mのコンピュータへのパスをなくしたい。 コンピュータとケーブ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2251N件の家がM本の道でつながっている。 L個のプレゼントを届ける家の番号と届ける時間が与えられる。 プレゼントを予定通りに届けることができる最小のサンタの人数を求める問題。 https…