UVa 12972 - Cuban Challenge

Source

Regional WarmUp(20151024)
(Competitive Programming Network - Eleventh Activity - 2015, Premio Fase II México & Centroamérica The ACM-ICPC in ESCOM-IPN 2015)
UVa 12972

問題概要

$N$ 行 $M$ 列の盤面が与えられ,各セルは白か黒に塗られている.
$1 \times 2$ のサイズのドミノを置いていくが,ドミノは重なってはならず,また,黒いセルには置いてはいけず,白いセルを全部覆っていなければいけない.
ドミノは縦向きにも横向きにも使え,コストを $1$ 支払うことで,$1 \times 1$ のサイズのドミノ $2$ 個に切ってもらえる.
最小コストを求める問題.

解法

各セルを市松模様に分け,二部グラフを作り,最大マッチングを求めることで,最大でドミノ切らずにいくつ置くことができるかを求めることができる.
二部グラフの最大マッチングは最大流で求めることができる.
後は,いくつ白いセルをカバーできていないかがわかるので,その分はドミノを切れば良い.
よって,ノード数も枝数も $O(NM)$ 程度のグラフの最大流を求める問題になるが,Dinicで十分間に合った(制限時間 $2$ 秒のところ,$0.1$ 秒以下で通った).

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年07月21日13時31分29秒
Last modified: 2015年11月02日15時16分06秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151024_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: