12/30 PKU
1466 Girls and Boys
N人の生徒がいて、いくつかの男女の間に「ロマンチックな関係」がある。これらの生徒の中から何人か選んで、どの2人の間にも「ロマンチックな関係」がないようにするとき、最大で何人選べるか。
まずDFSして生徒の性別を確定させる(ロマンチックな関係がある同士で異なりさえすればなんでもいい)。その後男女間で二部マッチングをし、その答えをNから引くと求まる。
1091 跳蚤
中国語が読めないが、ものすごくかいつまんで言うと「整数が書かれたカードがn+1枚あり、1〜n枚目には1〜Mのうちどれかが、n+1枚目にはMが書かれている。n+1枚に書かれている数の最大公約数が1になるような、カードの組み合わせは何通りか求めよ。」
任意のkに対して、「最大公約数がkの倍数になる」場合はすぐに求まるので、それを用いて包除原理的なことをする。
1254 Hansel and Grethel
ある座標から、すでに分かっている2つの座標までの角度が与えられるので、元の座標を特定せよ。
2直線の交点求めるだけ
2135 Farm Tour
グラフ上で、頂点1から頂点Nまでの2つの経路で、同じ辺を通らないもののうち、最も距離の和が短いものの距離を求めよ。
最小費用流やるだけ
3686 The Windy's
おもちゃを修理する。おもちゃと修理人によって、修理にかかる時間が違う。すべてのおもちゃが修理されるまでにかかる時間の平均値を最小化せよ。
最小費用流。例えば、あるおもちゃがある修理人によって時間Tをかけて修理された後、さらに3つのおもちゃをその修理人が修理したとすると、そのおもちゃは全部で4Tの時間を消費したと考える。すると、各修理人ごとにT,2T,…,NTの時間を消費する修理人を仮想し(それぞれ1つのおもちゃしか修理できない)、最小費用流を用いて最適な割り当てを求めると解ける。
2195 Going Home
家と人が同じ数ある。人が家に帰る。それぞれの家には１人しか帰れない。移動距離（家と人の間のマンハッタン距離）の総和を最小化せよ。
家から人で最小費用流
1422 Air Raid
閉路のない有向グラフが与えられる。落下傘部隊がいつかの頂点に降り、辺を伝って移動する。すべての頂点をちょうど１人の落下傘部隊が訪れるようにするとき、最低何人必要か求めよ。
辺(i, j)に対して、i -> j' の辺を張ったものを使って二部マッチング。
2060 Taxi Cab Scheme
タクシーの客扱いリスト（到着時刻と、起点と、終点）が与えられる。各タクシーは、起点に到着して１分後から次の客扱いを始められる。何台のタクシーが必要か。
グラフを作成し、1422と同じことをやる。
