2019-06-27から1日間の記事一覧
問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2691 解法 流量1ずつ流していったときの最小費用流のコストのグラフは、下に凸な折れ線グラフになる。 求める値は、このグラフと点 \((M, 0)\) との距離であり、グラフの形からこの距離も…
問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2202 解法 全長が小さいので DP する。 reach[i][j] := 船 i が位置 j に到達する最短時刻これはあくまでも「到達」時刻であり、その地点を出発できる時刻ではない(門の上下などで停泊す…