「Luogu3231」 [HNOI2013]消毒

problem

题目描述

最近在生物实验室工作的小T遇到了大麻烦。 由于实验室最近升级的缘故，他的分格实验皿是一个长方体,其尺寸为a*b*c，a、b、c 均为正整数。为了实验的方便，它被划分为a*b*c个单位立方体区域，每个单位立方体尺寸为1*1*1。用(i,j,k)标识一个单位立方体，1 <=i<=a，1<=j<=b，1<=k<=c。这个实验皿已经很久没有人用了，现在，小T被导师要求将其中一些单位立方体区域进行消毒操作（每个区域可以被重复消毒）。

而由于严格的实验要求，他被要求使用一种特定 的F试剂来进行消毒。 这种F试剂特别奇怪，每次对尺寸为x*y*z的长方体区域（它由x*y*z个单位立方体组 成）进行消毒时，只需要使用min{x,y,z}单位的F试剂。F试剂的价格不菲，这可难倒了小T。

现在请你告诉他，最少要用多少单位的F试剂。(注：min{x,y,z}表示x、y、z中的最小者。)

输入格式：

第一行是一个正整数D，表示数据组数。接下来是D组数据，每组数据开头是三个数a,b,c表示实验皿的尺寸。接下来会出现a个b 行c列的用空格隔开的01矩阵，0表示对应的单位立方体不要求消毒，1表示对应的单位立方体需要消毒；例如，如果第1个01矩阵的第2行第3列为1，则表示单位立方体(1,2,3)需要被消毒。输入保证满足a*b*c<=5000,T<=3。

输出格式：

仅包含D行，每行一个整数，表示对应实验皿最少要用多少单位的F试剂。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
4  4 4
1  0 1 1
0  0 1 1
0  0 0 0
0  0 0 0
0  0 1 1
1  0 1 1
0  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
1  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
0  0 0 0
1  0 0 0

输出样例#1：

1
3

说明

对于区域(1,1,3)-(2,2,4)和(1,1,1)-(4,4,1)消毒，分别花费2个单位和1个单位的F试剂。

Solution

一次消毒的花费是长宽高中的最小者，那么我们强制每次消毒代价均为1，即每次仅涉及到所有横（竖、纵）坐标相同的方格

我们来思考一下二维平面的情况，每次消毒的代价为长宽中的最小值，策略跟上面一样

如果我们把每个需要消毒的区域当做边，其横、纵坐标是边的端点，那么对于每条边，它的两个端点至少要选中一个

眼熟吗？这就是二分图最小点覆盖

根据König定理，二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数

二维平面上的情况是十分显然的，到了三维就不能直接这么做了

注意到a∗b∗c≤5000;a,b,c∈N∗a*b*c\le5000;a,b,c\in \mathbb{N^*}，所以min(a,b,c)≤17min(a,b,c)\le17

于是我们可以把实验皿放倒（使长度最小的维度作为竖直方向上的维度）

先选若干层进行消毒（把若干层上的待消毒方格去掉）

然后一巴掌拍扁实验皿（剩余的待消毒方格映射到二维平面内）

再跑二分图匹配就行了

那……怎么选出提前消毒的若干层呢

搜索啊

时间复杂度O(2min(a,b,c)∗a∗b∗cmin(a,b,c))O(2^{min(a,b,c)}*\frac{a*b*c}{min(a,b,c)})

Code

巨丑无比，极度不建议阅读
注意不能用memset清零，分分钟TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define maxabc 5005
#define minabc 25
using namespace std;
typedef long long ll;

template <typename T>void read(T &t)
{
	t=0;char c=getchar();int f=0;
	while(!isdigit(c)){f|=c=='-';c=getchar();}
	while(isdigit(c)){t=t*10+c-'0';c=getchar();}
	if(f)t=-t;
}

int D;

int a,b,c;
int cnt,ans;
int x[maxabc],y[maxabc],z[maxabc];
int sel[minabc];

struct edge
{
	int u,v,nxt;
}g[maxabc];

int head[maxabc],ecnt;
void eADD(int u,int v)
{
	g[++ecnt].u=u;
	g[ecnt].v=v;
	g[ecnt].nxt=head[u];
	head[u]=ecnt;
}

void Build()
{
	for(register int i=1;i<=ecnt;++i)
		g[i].u=g[i].v=g[i].nxt=0;
	for(register int i=1;i<=cnt;++i)
		head[i]=0;
	ecnt=0;
	for(register int i=1;i<=cnt;++i)
	{
		if(sel[z[i]])
			continue;
		eADD(x[i],y[i]);
	}
}

int result[maxabc],use[maxabc],sign;
bool Hungary(int u)
{
	for(register int i=head[u];i;i=g[i].nxt)
	{
		int v=g[i].v;
		if(use[v]==sign)
			continue;
		use[v]=sign;
		if(!result[v] || Hungary(result[v]))
		{
			result[v]=u;
			return true;
		}
	}
	return false;
}

int Calc()
{
	for(register int i=1;i<=cnt;++i)
		result[i]=use[i]=0;
	int re=0;
	for(register int i=1;i<=b;++i)
	{
		sign=i;
		re+=Hungary(i); 
	}
	return re;
}

void dfs(int step,int select)
{
	if(step==a+1)
	{
		Build();
		ans=min(ans,select+Calc());
		return;
	}
	sel[step]=1;
	dfs(step+1,select+1);
	sel[step]=0;
	dfs(step+1,select);
}

void Work()
{
	read(a),read(b),read(c);
	cnt=0,ans=0x7f7f7f7f;
	for(register int i=1;i<=a;++i)
		for(register int j=1;j<=b;++j)
			for(register int k=1;k<=c;++k)
			{
				int d;read(d);
				if(d)z[++cnt]=i,x[cnt]=j,y[cnt]=k;
			}
	if(min(a,min(b,c))==b)
	{
		swap(a,b);
		for(register int i=1;i<=cnt;++i)swap(z[i],x[i]);
	}
	else if(min(a,min(b,c))==c)
	{
		swap(a,c);
		for(register int i=1;i<=cnt;++i)swap(z[i],y[i]);
	}
	dfs(1,0);
	printf("%d\n",ans);
}

int main()
{
	read(D);
	while(D--)
		Work();
	return 0;
}