「Bzoj 3410」「HNOI2013」消毒 (最小点覆盖)

发表于 | 分类于 | | + s

BZOJ 3410
题意：有一个长方体，有一些格子上有$1$，你可以进行$k$次操作，每次选择一个长方体区域$(x,y,z)$，代价为$\min(x,y,z)$，可以将这个区域所以$1$改为$0$，求最小的$k$使得整个长方体都为$0$

先是要发现代价为$\min(x,y,z)$其实就意思是，我们选择一个代价不为$1$的操作，都可以转化成若干代价为$1$的操作，并且答案不会更差。所以这题就是一个三维的poj 3041。

然而三维并不能三分图，那么我们发现题目给的数据范围$A\cdot B \cdot C \leq 5000$，那么必然有一个数小于$\sqrt[3]{5000} \approx 17$，所以我们假设$A$就是这个最小的数(不是的话可以交换坐标，几何意义就是将长方体换个方向)。那么暴力枚举每一层是否操作，然后再将另外两维做平面上最小点覆盖即可。

知识点
1、隐含小数据：乘积

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

int T;

namespace flyinthesky {

    const int MAXN = 5000 + 5;

    struct EDGE {
        int v, nxt;
    } ED[MAXN];
    int EN, HD[MAXN];

    int A, B, C, oA, oB, oC;
    int lk[MAXN], vis[MAXN], cnt, ys[4], tot;

    struct edge {
        int pos[4];
    } ed[MAXN];

    bool hungary(int u) {
        for (int i = HD[u]; i >= 0; i = ED[i].nxt) {
            int v = ED[i].v;
            if (vis[v] != cnt) {
                vis[v] = cnt;
                if (!lk[v] || hungary(lk[v])) {
                    lk[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    void ins(int x, int y) {ED[++EN] = (EDGE){y, HD[x]}, HD[x] = EN;}

    void clean() {
        tot = 0;
    }
    int solve() {

        clean();
        scanf("%d%d%d", &A, &B, &C), oA = A, oB = B, oC = C;
        ys[0] = 0, ys[1] = 1, ys[2] = 2;
        if (B > A) swap(A, B), swap(ys[0], ys[1]);
        if (C > A) swap(A, B), swap(ys[0], ys[2]);

        for (int i = 1; i <= oA; ++i) {
            for (int j = 1; j <= oB; ++j) {
                for (int x, k = 1; k <= oC; ++k) {
                    scanf("%d", &x);
                    if (x == 1) {
                        ++tot;
                        ed[tot].pos[ys[0]] = i;
                        ed[tot].pos[ys[1]] = j;
                        ed[tot].pos[ys[2]] = k;
                    }
                }
            }
        }

        int ans = 2000000000;

        for (int S = 0; S < (1 << A); ++S) {
            EN = -1;
            for (int i = 0; i <= B; ++i) HD[i] = -1;
            for (int i = 0; i <= C; ++i) vis[i] = lk[i] = 0;
            int whw = 0;
            for (int tmp = S; tmp; tmp &= (tmp - 1)) ++whw;
            for (int i = 1; i <= tot; ++i) {
                if (!(S & (1 << (ed[i].pos[0] - 1)))) {
                    ins(ed[i].pos[1], ed[i].pos[2]);
                } 
            }
            int ret = 0;
            for (int i = 1; i <= B; ++i) if (hungary(cnt = i)) ++ret;
            ans = min(ans, ret + whw);
        }

        cout << ans << endl;

        return 0;
    }
}
int main() { 
    //freopen("1.in", "r", stdin);
    cin >> T;
    while (T--) flyinthesky::solve();
    return 0;
}
/*
10
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

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

3 2 1
1
0

1
1

0
0
*/
------ 本文结束 ------