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がきついのでがんばること。