「WC2016」 挑战NPC

发表于 | 更新于 | 分类于 ，

$\Large\mathcal{Description}$

有 $n$ 个球和 $m$ 个筐子。

每个筐里最多能装三个。如果一个筐子内有不超过 $1$ 个球，那么我们称这样的筐子为半空的。

每个球都必须放进一个筐子中。且对于每个球有一些限制，即能放进哪个筐里。

现要求半空的筐最多有几个，并输出方案。

小 I 浅笑：“所以，等我领图灵奖吧！”

$\Large\mathcal{Solution}$

机房大佬介绍的一道题 刚学的带花树，但发现基本找不到题

首先，每个筐里最多放三个球。我们可以把每个筐拆成三个点，再把每个球作为一个点。这样，用我们最终得出的方案构成的图中，每个点的度数一定都不会超过1

这就与一般图的最大匹配相似，但我们显然不能直接跑一遍带花树。因为装有一个球以上的筐会对答案造成影响。所以我们必须操作一下

有一种很妙的想法就是， 在每个筐拆出的三个点之间互相连边。$\mathcal{Why?}$

我们依次进行考虑

  • 非半空的筐子(即装有 $2$ 或 $3$ 个球)。他们对答案作出的贡献是无意义的，所以要减去。而他们对答案的影响就是装有的球数。
  • 装有 $1$ 个球的筐子。他们对答案应作出 $1$ 的贡献。但由于筐的三个点之间有连边，所以他们对当前答案(即带花树跑出来的结果)贡献是 $2$。所以减 $1$。
  • 空的筐。他们对答案应作出 $1$ 的贡献。但由于筐的三个点之间有连边，所以他们对当前答案的贡献是 $1$。所以不变。

归纳一下就可以得到，一个筐内装有多少球，他就对最终答案造成了多少影响。

由于每个球都必须放入一个筐子, 所以，最终答案就等于带花树跑出来的答案减去 $n$。

$\Large\mathcal{Code}$

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
//冗长的代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
template <typename Tp>
inline void read(Tp &x) {
    x = 0;
    bool f = true; char ch = getchar();
    for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
    for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
    x = f ? x : -x;
}

const int N = 1005, M = 2e5 + 7;

int head[N], cnt = 0;

struct edge {
    int to, next;
};
edge e[M << 1];

inline void add_edge(int x, int y) {
    e[++cnt] = (edge) {y, head[x]}, head[x] = cnt;
}

int fa[N], pre[N], f[N], tic[N], tim = 0, m, vis[N];
std::queue <int> q;

inline int father(int x) {
    return fa[x] == x ? x : fa[x] = father(fa[x]);
}

inline void shrink(int x, int y, int top) {
    while (father(x) != top) {
        pre[x] = y, y = f[x];
        if (vis[y] == 2) vis[y] = 1, q.push(y);
        if (father(x) == x) fa[x] = top;
        if (father(y) == y) fa[y] = top;
        x = pre[y];
    }
}

inline int LCA(int x, int y) {
    ++tim;
    while (1) {
        x = father(x);
        if (tic[x] == tim) return x;
        else tic[x] = tim, x = pre[f[x]]; 
        std::swap(x, y);
    }
}

inline bool match(int s) {
    for (int i = 1; i <= m; ++i) fa[i] = i;
    std::fill(pre + 1, pre + m + 1, 0);
    std::fill(vis + 1, vis + m + 1, 0);
    while (q.size()) q.pop();
    vis[s] = 1, q.push(s);
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            int v = e[i].to;
            if (vis[v] == 2 || father(x) == father(v)) continue;
            if (!vis[v]) {
                vis[v] = 2, pre[v] = x;
                if (!f[v]) {
                    for (int cur = v, last; cur; cur = last) {
                        last = f[pre[cur]];
                        f[pre[cur]] = cur, f[cur] = pre[cur];
                    }
                    return true;
                }
                vis[f[v]] = 1, q.push(f[v]);
            }
            else if (vis[v] == 1) {
                int lca = LCA(x, v);
                shrink(x, v, lca);
                shrink(v, x, lca);
            }
        }
    }
    return false;
}

int main() {
    int T;
    read(T);
    while (T--) {
        int n, E;
        read(n), read(m), read(E);
        cnt = tim = 0;
        std::fill(head + 1, head + n + 3 * m + 1, 0);
        std::fill(f + 1, f + n + 3 * m + 1, 0);
        std::fill(tic + 1, tic + n + 3 * m + 1, 0);
        for (int i = 1; i <= E; ++i) {
            int x, y;
            read(x), read(y);
            int z = n + (y - 1) * 3;
            add_edge(x, z + 1), add_edge(z + 1, x);
            add_edge(x, z + 2), add_edge(z + 2, x);
            add_edge(x, z + 3), add_edge(z + 3, x);
        }
        for (int i = 1; i <= m; ++i) {
            int x = n + (i - 1) * 3;
            add_edge(x + 1, x + 2), add_edge(x + 2, x + 1);
            add_edge(x + 1, x + 3), add_edge(x + 3, x + 1);
            add_edge(x + 2, x + 3), add_edge(x + 3, x + 2);
        }
        int ans = -n;
        m = m * 3 + n;
        for (int i = 1; i <= m; ++i) ans += (!f[i] && match(i));
        printf("%d\n", ans);
        for (int i = 1; i <= n; ++i) printf("%d%c", (f[i] - n - 1) / 3 + 1, " \n"[i == n]);
    }
    return 0;
}

$\huge\mathcal{CSP 2019}$ $\huge\color{red}{\mathcal{R}}\color{yellow}{\mathcal{P}}\color{orange}{++}$