BZOJ3140 消毒

BZOJ3140 消毒

题意

最近在生物实验室工作的小T遇到了大麻烦。
由于实验室最近升级的缘故，他的分格实验皿是一个长方体,其尺寸为abc，a、b、c 均为正整数。为了实验的方便，它被划分为abc个单位立方体区域，每个单位立方体尺寸
为111。用(i,j,k)标识一个单位立方体，1 ≤i≤a，1≤j≤b，1≤k≤c。这个实验皿已经很久没有人用了，现在，小T被导师要求将其中一些单位立方体区域进 行消毒操作（每个区域可以被重复消毒）。而由于严格的实验要求，他被要求使用一种特定 的F试剂来进行消毒。 这种F试剂特别奇怪，每次对尺寸为xyz的长方体区域（它由xyz个单位立方体组 成）进行消毒时，只需要使用min{x,y,z}单位的F试剂。F试剂的价格不菲，这可难倒了小 T。现在请你告诉他，最少要用多少单位的F试剂。(注：min{x,y,z}表示x、y、z中的最小 者。)
abc≤5000,T≤3。

题解

首先是前置知识（原本啥都不会想题直接自闭）

1.二分图最小点覆盖=二分图最大匹配
设二分图最大匹配为x，二分图最小点覆盖为y，首先显然 x ≤ y x\le y x≤y，考虑对于一条匹配边，它的两个端点不会都连向其他未匹配点（否则交换更优），所以定一个点为匹配点即可覆盖。

2.二分图最小边覆盖=点数-二分图最大匹配
每个点都先选，减掉每个最大匹配的一个端点，每条边的两个端点显然不会同时被选。

3 二分图最大独立集=点数-二分图最大匹配
去掉最小点覆盖的点后，每条边不会连接剩下的任意两个点，就是最大独立集了。

首先肯定是每次取一个面，发现如果是二维就是一个二分图最小点覆盖，而三维不太可做。注意到数据范围 a b c ≤ 5000 abc\le5000 abc≤5000，一定会有一维 ≤ 17 \le17 ≤17，枚举这一维每个面是否选，再做二分图匹配即可。