Bring Them There (UVa Live Archive Europe - Northeastern - 2003/2004 St. Petersburg (Russia))
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2957
問題
N頂点、辺数Mのグラフがある。SからTへスパコンをK台運びたい。ただし、スパコンを隣の頂点へ運ぶのに1日かかり、一つの辺では1日に1台のスパコンを通すことしか出来ない。スパコンを全て運ぶのにかかる日数とそれの段組を答えよ。
2<=N<=50
1<=M<=200
1<=K<=50
1<=S,T<=N
S!=T
解法
日にちによって頂点・辺を増やして最大流を流す。一つの辺が両方の向きで使われると困るので頂点を2つ増やして処理する。TLEがきついのでがんばること。