BZOJ 3140: [Hnoi2013]消毒

每次消的一定是1*N*N的一块
因为如果某次删的最小边是k
那么另外两条边一定是取到最大
对于这个清洗 可以分成k个1*N*N的步骤
考虑到最小的边长最大只会有17
可以枚举这个维度哪些要取
然后就变成了经典的棋盘最小覆盖问题
可以用二分图匹配做
对于点(x,y)连接左部x点和右部的y的点
最大匹配即为ans
这题卡常数
卡得还非常没节操
看了它的数据 里面1的个数非常少
所以对每行 哪几列有1 用链表存储 就可以过了

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
134
135
136
137
138
139
140
141
142
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 5005;

struct line
{
  int to, next;
}li[maxn * 10], li2[maxn * 1000];

int x, y, z, a[maxn], t[maxn], b[20], ans, fa[maxn], be[maxn], br[maxn], l, be2[maxn], l2;

void makeline(int fr, int to)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}

void makeline2(int fr, int to)
{
  ++l2;
  li2[l2].next = be2[fr];
  be2[fr] = l2;
  li2[l2].to = to;
}

bool can(int now)
{
  br[now] = 1;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (fa[to] == -1 || (!br[fa[to]] && can(fa[to])))
    {
      fa[to] = now;
      return true;
    }
  }
  return false;
}

int check()
{
  for (int i = 0; i < z; ++i) fa[i] = -1;
  for (int i = 0; i < y; ++i) be[i] = 0;
  l = 0;
  for (int i = 0; i < x; ++i)
    if (!b[i])
      for (int j = 0; j < y; ++j)
        for (int k = be2[i * y + j]; k; k = li2[k].next)
        {
          int to = li2[k].to;
          makeline(j, to);
        }
  int ans = 0;
  for (int i = 0; i < y; ++i)
  {
    for (int j = 0; j < y; ++j) br[j] = 0;
    if (can(i)) ++ans;
  }
  return ans;
}

void dfs(int now, int tot)
{
  if (now == x)
  {
    ans = min(ans, check() + tot);
    return;
  }
  b[now] = 1;
  dfs(now + 1, tot + 1);
  b[now] = 0;
  dfs(now + 1, tot);
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
  scanf("%d%d%d", &x, &y, &z);
  memset(be2, 0, sizeof(be2));
  l2 = 0;
  for (int i = 0; i < x * y * z; ++i) scanf("%d", &t[i]);
  if (x <= y && x <= z)
  {
    for (int i = 0; i < x; ++i)
      for (int j = 0; j < y; ++j)
        for (int k = 0; k < z; ++k)
          a[i * y * z + j * z + k] = t[i * y * z + j * z + k];
  }
  else
  if (z <= x && z <= y)
  {
    for (int i = 0; i < x; ++i)
      for (int j = 0; j < y; ++j)
        for (int k = 0; k < z; ++k)
          a[k * y * x + j * x + i] = t[i * y * z + j * z + k];
    int tx = x, ty = y, tz = z;
    x = tz, y = ty, z = tx;
  }
  else
  if (y <= z && y <= x)
  {
    for (int i = 0; i < x; ++i)
      for (int j = 0; j < y; ++j)
        for (int k = 0; k < z; ++k)
          a[j * x * z + i * z + k] = t[i * y * z + j * z + k];
    int tx = x, ty = y, tz = z;
    x = ty, y = tx, z = tz;
  }
  ans = 0x7fffffff;
  for (int i = 0; i < x; ++i)
    for (int j = 0; j < y; ++j)
      for (int k = 0; k < z; ++k)
        if (a[i * y * z + j * z + k])
          makeline2(i * y + j, k);
  dfs(0, 0);
  printf("%d\n", ans);
  }
}

发表评论