AtCoder Regular Contest 074：F - Lotus Leaves

問題

https://atcoder.jp/contests/arc074/tasks/arc074_d

考え方

最小カットということがわかるので、最大フローを求めればよいのだが、辺の張り方が難しい

  • マス (h_i, w_i) について、o のとき h_i から w_i へコスト1の辺
  • マス S のとき src から h_i と w_i へコストINFの辺
  • マス T のとき h_i と w_i から dst へコストINFの辺

を張ったときのグラフを考えると、もとのグリットと同一視できる。

あとはこのグラフ上の最大フローを求めれば良い。

Submission #4120333 - AtCoder Regular Contest 074

どこに着目して考察するべきだったか

グラフの作り方。H軸とW軸で分けて、HからWへの辺を考える、、、

何がバグっていたか

得た知見(典型ポイント)

  • 頂点倍化
  • グリッド上の2軸で軸から軸への辺を考える

類題