【BZOJ3140】【HNOI2013】消毒

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

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

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

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

1
说点什么

1 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

Orz