[HNOI 2013] 消毒 （搜索，二分图匹配）
2024-08-29 10:05:57
题目大意
一个a * b * c（a * b * c <= 5000）大小的长方体中有一些点需要被覆盖，每次可以选择任意大小的长方体，覆盖其中的点，产生的代价为这个长方体长宽高中最小的那个的长度，求最小代价。
二维情形
对二维的情形这就是经典的最小割问题了，可以建立二分图用二分图最大匹配算法解决。具体建图方法是将行和列分为两个集合，如果一个点需要被覆盖，就将它所在的行和列连接起来。这种解法的正确性是显然的：由最大流-最小割定理，最大流就等于最小割，而将行和列连起来后，为保证源与汇分开必须将源到行的边或者列到汇的边割掉。
错误解法
这题我一开始其实就想偏了，我认为可以像二维情形那样直接建立最小割模型求解。我想的是：每个点都有三种选择，故仅需将对应几个分量的点连起来跑最小割就行了。但实际上这是错的。原因是这种建模方式会使得它表示的限制比实际要求的更紧（每个限制就是某些边里至少要割掉一条边，这样建模会使这种限制增多），从而使答案偏大。
正解
因为a * b * c <= 5000，所以min{a, b, c} <= 17，我们可以对其中一维直接暴力搜索枚举所有情形，剩下的问题便是二维的了，直接用刚才的建模方式就行了。
最新文章
- Java中OutOfMemoryError(内存溢出)的三种情况及解决办法
- Java多线程初探
- express 框架之session
- Web Uploader - 功能齐全，完美兼容 IE 的上传组件
- 今天想用jquery来实现div的拖放功能
- MVC2.0前置
- Top 10 Programming Fonts
- Android NDK环境配置
- 10、JPA_映射双向多对多的关联关系
- HDU 4099 Revenge of Fibonacci （数学+字典数）
- DOS环境下MySQL使用及不同字符集之间的转换
- BZOJ 2626 JZPFAR（KD-tree）
- 浅谈hadoop中mapreduce的文件分发
- TI C66x DSP 系统events及其应用 - 5.8（ISTP）
- LinbDesk --- 新的extjs4.2 desktop demo : 技术交流Q群：336584192
- verilog中24LC04B iic(i2c)读写通信设计步骤，以及程序常见写法错误。
- C#常用的命名规则汇总
- 泡泡一分钟：Cubic Range Error Model for Stereo Vision with Illuminators
- C、C++ 学习经历
- Unable to cast object of type 'System.Int32' to type 'System.Array'.