关于
联系
Oi大佬们
keyboard_arrow_down
本站已运行
载入天数...载入时分秒...
Woshiluo's Notebook
Woshiluo
2019年1月8日
Luogu P3231 [HNOI2013]消毒 — 二分图匹配

题目

题目链接: [https://www.luogu.org/problemnew/show/P3231]

先考虑一下,如果这张图是一个二维的情况?

对于每一个需要消毒的点的 $x,y$ 相互链接,然后直接跑最小点覆盖就对了

三维的情况?

三分图匹配?

不会,但是显然我们可以知道,如果我们设$ x $为三边中最小值则
$$ x \leq \sqrt[3]{5000} $$
也就约等于$$ x \leq 17$$

直接$ 2^{17} $ 枚举每一层选或者不选即可….

代码

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

inline int Min(int a, int b) { return a < b ? a : b; }

const int N = 5e3 + 1e2;
const int INF = 0x4fffffff;

int T, u, v, w, op, res, ans;
int len[3], vis[30], match[30], vcnt, pos;
bool chose[30];

// edge start
struct edge {
    int to, next, val;
} e[N << 1];
int ehead[N], ecnt;
inline void add_edge(int now, int to, int val) {
    ecnt++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// edge end

inline void init() {
    memset(vis, 0, sizeof(vis));
    memset(ehead, 0, sizeof(ehead));
    ecnt = vcnt = 0;
    ans = INF;
}

inline void readin() {
    scanf("%d%d%d", &len[0], &len[1], &len[2]);
    if (len[0] <= len[1] && len[0] <= len[2])
        pos = 0;
    else if (len[1] <= len[2] && len[1] <= len[0])
        pos = 1;
    else
        pos = 2;
    for (int i = 1; i <= len[0]; i++) {
        for (int j = 1; j <= len[1]; j++) {
            for (int k = 1; k <= len[2]; k++) {
                scanf("%d", &op);
                if (!op)
                    continue;
                if (pos == 0)
                    add_edge(j, k, i);
                else if (pos == 1)
                    add_edge(k, i, j);
                else if (pos == 2)
                    add_edge(i, j, k);
            }
        }
    }
}

bool eft(int now) {
    for (int i = ehead[now]; i; i = e[i].next) {
        if (!chose[e[i].val] && vis[e[i].to] < vcnt) {
            vis[e[i].to] = vcnt;
            if (!match[e[i].to] || eft(match[e[i].to])) {
                match[e[i].to] = now;
                return true;
            }
        }
    }
    return false;
}

inline int get_ans(int now) {
    res = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= len[(pos + 1) % 3]; i++) {
        vcnt++;
        if (eft(i))
            res++;
        if (res + now >= ans)//最优化剪枝
      return ans;
    }
    return res + now;
}

void dfs(int now, int sum) {
    if (now > len[pos]) {
        ans = Min(get_ans(sum), ans);
        return;
    }
    chose[now] = 1;
    dfs(now + 1, sum + 1);
    chose[now] = 0;
    dfs(now + 1, sum);
}

inline void work() {
    dfs(1, 0);
    printf("%d\n", ans);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("bzoj.3140.in", "r", stdin);
    freopen("bzoj.3140.out", "w", stdout);
#endif
    scanf("%d", &T);
    while (T--) {
        init();
        readin();
        work();
    }
}

textsms