【BZOJ3140】【HNOI2013】消毒

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

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

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

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

Subscribe
提醒
1 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
LCF
3 年 之前

Orz

1
0
Would love your thoughts, please comment.x
()
x