[HNOI 2013] 消毒 (搜索,二分图匹配)

题目大意

一个a * b * c(a * b * c <= 5000)大小的长方体中有一些点需要被覆盖,每次可以选择任意大小的长方体,覆盖其中的点,产生的代价为这个长方体长宽高中最小的那个的长度,求最小代价。

二维情形

对二维的情形这就是经典的最小割问题了,可以建立二分图用二分图最大匹配算法解决。具体建图方法是将行和列分为两个集合,如果一个点需要被覆盖,就将它所在的行和列连接起来。这种解法的正确性是显然的:由最大流-最小割定理,最大流就等于最小割,而将行和列连起来后,为保证源与汇分开必须将源到行的边或者列到汇的边割掉。

错误解法

这题我一开始其实就想偏了,我认为可以像二维情形那样直接建立最小割模型求解。我想的是:每个点都有三种选择,故仅需将对应几个分量的点连起来跑最小割就行了。但实际上这是错的。原因是这种建模方式会使得它表示的限制比实际要求的更紧(每个限制就是某些边里至少要割掉一条边,这样建模会使这种限制增多),从而使答案偏大。

正解

因为a * b * c <= 5000,所以min{a, b, c} <= 17,我们可以对其中一维直接暴力搜索枚举所有情形,剩下的问题便是二维的了,直接用刚才的建模方式就行了。

[HNOI 2013] 消毒 (搜索,二分图匹配)

上一篇:配置MVC模式WebApplication及应用上下文关联的方法


下一篇:(转)ligerUI 使用教程之Tip介绍与使用