Warning: session_start(): open(/tmp/sess_4871eef4d66ffc51f66ce52e427a67f8, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
[[http://bestcoder.hdu.edu.cn/contests/contest_showproblem.php?cid=889&pid=1007|题面]]
====简单题意====
房间是个 $n\times m$ 的网格,一共有 $k$ 个窗户,都在上下左右四条边上。在第 $0$ 时刻,每个窗户对应的格子上都会出现若干只蚊子。
\\
蚊子每个时刻可以往上下左右移动一格或者呆在原地不动。
\\
假设这些蚊子都足够聪明,请问最少花费多少时刻,使得所有格子上都有至少一只蚊子?
\\
蚊子在第 $0$ 时刻不能动。
\\
$n,m,k(1\leq n,m\leq 1000,1≤k≤6)$
====简单题解====
二分答案,把每个点映射到对应的 $2^k$ 状态节点中(容量$+1$),每个窗格往对应可达状态节点($\text{该位}=1$)连边,网络流检验答案合法性。
@ws_zzyer 表示可以用霍尔定理替代网络流检验答案,待尝试!