【BZOJ3140】【HNOI2013】消毒

劲啊。。又是一道我想不出的网络流

首先最优的做法一定是每次选择一边长度为\(1\)另外两边长度最大的一个区域,很显然。

如果只有两个坐标,那么建一个二分图,对于每一个点\((x_i,y_i)\),从\(x_i\)向\(y_i\)连边表示这两个中必须选择一个,转化为二分图最小覆盖。跑一遍最大匹配就行了。

对于三个坐标,第一步也是最关键的一步,我们发现最小的那一维的长度一定不大于\(\lfloor\sqrt[3]{5000}\rfloor=17\)。那么枚举最小那一维的选择情况再处理剩下两维即可。

说点什么

1 评论 在 "【BZOJ3140】【HNOI2013】消毒"

提醒
排序:   最新 | 最旧 | 得票最多
成员

Orz

wpDiscuz