Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

ネットワークフロー

AOJ 0247 - Arts and Crafts

問題文 : 図画工作解法 :$dp[i][j][k]$ : $i$ で表される道具の集合をを$j$ 日目に$k$ 個まで道具をかって実現することができるか, として事前にDP を行う.それで, 袋から完成状態へDP の結果をコストとする辺を貼り, 流量を$N$ とした最小費用流を行う.

AOJ 2457 - Adhoc Translation

問題文 : Adhoc Translation解法 : これがA 問題ってやべえなあ... 辞書に登録されている単語とネットで見た単語の間に, それぞれ編集距離をコストとした辺を張る. ネットで見た単語の数 ≦ 辞書に登録されている単語の数で, かならずネットで見た単語の数の…