Pool construction (UVa Live Archive Europe Northwestern 2011)
問題
w*hのグリッドにプールを作りたい。#のセルを.に変えるコストはd、.のセルを#に変えるコストはf、最終的な状況で#と.のセルが隣接しているとbのコストがかかる。また、端のセルは#でなければならない。コストの最小値を求めよ。
2<=w,h<=50
1<=d,f,b<=10,000
解法
MinCutするだけ。
w*hのグリッドにプールを作りたい。#のセルを.に変えるコストはd、.のセルを#に変えるコストはf、最終的な状況で#と.のセルが隣接しているとbのコストがかかる。また、端のセルは#でなければならない。コストの最小値を求めよ。
2<=w,h<=50
1<=d,f,b<=10,000
MinCutするだけ。