[luoguP3231] [HNOI2013]消毒（最小点覆盖 + 状压）

传送门

考虑贪心，控制某一维为1，另两位最大是最优的，也就是一次选一个厚度为1的面

那么对于每个点，可以有3种面是可以选到它的

然后gg

考虑二维的状态，一个平面，有些点，一次选一行或一列最优

那么每一个点i，j可以被行i和列j选中，将i>j连接一条边，每一条边就代表一个点

选取最少的点覆盖所有边就是最少点覆盖=最大匹配

因为a*b*c<=5000所以最小的那一维一定<=17，可以枚举这一维哪些面被一次清除，

#include <cstdio>#include <cstring>#include <iostream>#define N 5001using namespace std;int T, a, b, c, n, ans, cnt;int now[N][N], head[N], to[N * N], nex[N * N], belong[N];bool vis[N];struct node}p[N];inline int read()inline void clear()inline void add(int x, int y)inline bool dfs(int u)}}return 0;}inline int solve()ret = min(ret, ans);for(i = 1; i <= n; i++)if(!(k & (1 << p[i].x  1))) now[p[i].y][p[i].z] = 0;}return ret;}int main()if(c < a && c < b)else if(b < c && b < a)printf("%d\n", solve());}return 0;}

剩余的面压缩到一起，连边跑匈牙利

上一篇：[BZOJ3611] [Heoi2014]大工程（DP + 虚树）

下一篇：[luoguP2526] [SHOI2001]小狗散步（二分图最大匹配）