[BZOJ3140][Hnoi2013]消毒

首先由均值不等式可以得到，min{a, b, c} <= 17，不妨假设最短的那条边为a。接下来考虑消除，答案肯定不会超过a，因为可以做若干次1*b*c的消除。

一开始看到这个结论我还是非常傻逼的以为，只要把需要消毒的每一片1*b*c都消毒即可，还傻傻问副队哪来的二分图……经过副队的教导才意识到这样不一定最优，比较科学的做法是：2^a枚举每层是否消掉，然后用a*1*c和a*b*1的片覆盖，也就是转成二维的最小棋盘覆盖。

所谓最小棋盘覆盖就是说，每次可以覆盖掉棋盘的一整行或一整列，问把所有标记点覆盖的最小次数。嗯，这个也不会做……Google了一下，看到搜索结果里面最小点覆盖和行列拆开这两个关键词才突然意识到，这不就是个水水的二分图匹配嘛。

考虑把所有行放在左边，所有列放在右边，然后如果(i, j)需要被覆盖，那么连边(Xi, Yj)。之后就是一个最小点覆盖的问题了（选择最少的点，使得每条边都至少有一个端点被选择），因为最小点覆盖=最大匹配，所以轻松做掉了。（这个时候突然很庆幸前不久刚学匈牙利，明显这种时候用匈牙利跑匹配比网络流省事多了=v=）

常数

虽然写程序的时候已经在清数组的时候注意了，但是手测第一个点还是TLE得非常严重（吐槽一下，所有数据都是10K……）。后来看到副队博客上还有一句话，发现有一个非常卡BUG的优化方法：因为1的数量非常少，所以可以把1用链表串起来。嗯，加了优化后就可以过了。不知道不卡BUG是如何做的= =?

代码

bzoj3140[Hnoi2013]消毒 
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

#include <cstdio>
#include <cstring>
#include <algorithm>

struct Edge
{
  int v;
  Edge *next;
} g[10000], *header[5000], *head[5000];
int LinkSize, _link_size;
void AddEdge(Edge *&head, const int y)
{
  Edge* const node = g+(LinkSize++);
  node->v = y;
  node->next = head;
  head = node;
}
int T, a, b, c, ans, mat[5000], match[5000];
bool used[20], vis[5000];
inline int getid(const int x, const int y, const int z) { return x*b*c + y*c + z; }
bool find(const int u)
{
  for (Edge *e = header[u]; e; e = e->next)
  {
    if (vis[e->v]) continue;
    vis[e->v] = true;
    if (match[e->v] == -1 || find(match[e->v]))
    {
      match[e->v] = u;
      return true;
    }
  }
  return false;
}
void dfs(const int step, int cnt)
{
  if (cnt >= ans) return;
  if (step == a)
  {
    LinkSize = _link_size;
    memset(header, 0, sizeof(*header)*b);
    for (int j = 0; j < b; ++j)
      for (int k = 0; k < c; ++k)
      {
        bool flag = false;
        for (Edge *e = head[j*c+k]; e && !flag; e = e->next)
          flag = !used[e->v];
        if (!flag) continue;
        AddEdge(header[j], k);
      }
    memset(match, 0xFF, sizeof(*match)*c);
    for (int i = 0; i < b; ++i)
    {
      memset(vis, 0, sizeof(*vis)*b);
      if ((cnt += find(i)) >= ans) return;
    }
    ans = cnt;
    return;
  }
  used[step] = true; dfs(step+1, cnt+1);
  used[step] = false;dfs(step+1, cnt);
}
int solve()
{
  scanf("%d%d%d", &a, &b, &c);
  if (a <= b && a <= c)
    for (int i = 0; i < a; ++i)
      for (int j = 0; j < b; ++j)
        for (int k = 0; k < c; ++k)
          scanf("%d", mat+getid(i, j, k));
  else if (b <= a && b <= c)
  {
    std::swap(a, b);
    for (int j = 0; j < b; ++j)
      for (int i = 0; i < a; ++i)
        for (int k = 0; k < c; ++k)
          scanf("%d", mat+getid(i, j, k));
  }
  else
  {
    std::swap(a, c);
    for (int k = 0; k < c; ++k)
      for (int j = 0; j < b; ++j)
        for (int i = 0; i < a; ++i)
          scanf("%d", mat+getid(i, j, k));
  }
  LinkSize = 0;
  for (int j = 0; j < b; ++j)
    for (int k = 0; k < c; ++k)
    {
      head[j*c+k] = 0;
      for (int i = 0; i < a; ++i)
        if (mat[getid(i, j, k)])
          AddEdge(head[j*c+k], i);
    }
  _link_size = LinkSize;
  ans = a;
  dfs(0, 0);
  return ans;
}
int main()
{
  scanf("%d", &T);
  while (T--)
    printf("%d\n", solve());
}

Comments