Kuroni and Antihype | Codeforces 1305G

发表于 分类于 本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目链接

一张有 \(n\) 个点的图，每个点的点权为 \(a_i\)。

点 \(u\) 和点 \(v\) 连边当且仅当 \(a_u \& a_v = 0\)。

对于点 \(u\)，有两种操作：

  • 直接涂黑，无贡献。
  • 找一个与 \(u\) 相邻且已经涂黑的点 \(v\)，再涂黑 \(u\)，贡献为 \(a_v\)。

求涂黑所有点的最大贡献。

\(n \le 2 \cdot 10^5,a_i \le 2 \cdot 10^5\)

首先加入一个点权为 \(0\) 的虚点，且初始为黑，则两种操作就可以统一成第二种。

对于每次操作，就从 \(u\) 向 \(v\) 连一条有向边，得到一个以 \(0\) 为根的有根树。

设点 \(u\) 的度数为 \(degree_u\)，则总贡献可以表示为 \[ \sum_{u \in V}a_u(degree_u-1)=\sum_{u \in V}a_udegree_u-\sum_{u \in V}a_u = \sum_{(u,v) \in E}a_u + a_v - \sum_{u \in V}a_u \] 如果定义 \((u,v)\) 边权为 \(a_u + a_v\)，则前一部分为生成树权值，后一部分是定值。

所以问题转化为求最大生成树。

先考虑所有点的点权两两不同。

根据枚举子集的经典结论，边的总数小于 \(3^{18}\)，但实际只有一半左右，即 \(1.7 \cdot 10^8\) 左右。

考虑 Kruskal 算法，虽然并查集复杂度要乘一个 \(\alpha(n)\)，但感觉卡不满。

首先不可能存下所有边，更不可能排序，所以考虑从大到小枚举边权。

注意到 \(u,v\) 连边当且仅当 \(a_u \& a_v = 0\)，而边权为 \(a_u + a_v\)。

直接枚举边权的子集就可以得到两个端点。

剩下的正常做 Kruskal 就行了。

复杂度 \(O(3^{18}\alpha(n))\)。

点权相同时

当枚举到 \(a_u,a_v\) 时，\(a_u\) 可能会对应很多的 \(u\)，设这些 \(u\) 构成集合 \(U\)，\(a_v\) 也会对应很多的 \(a_v\)，设这些 \(v\) 构成集合 \(V\)。

任何一个 \(U\) 中的结点和任何一个 \(V\) 中的结点都有权值相等的连边，边太多了。

考虑一个等价的连边：

在 \(U\) 中选择一个代表元 \(u_0\)，同理选个 \(v_0\)，\(u_0\) 和 \(v_0\) 连边，\(u_0\) 和 \(U\) 中其他点连边，\(v_0\) 和 \(V\) 中其他点连边。

对于后两种连边，每个集合只用在第一次访问到时进行，复杂度 \(O(3^{18}\alpha(n))\)。

代码：

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
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)
#define For(i, l, r) for(int i = (l), i##e = (r); i < i##e; i++)
#define upd(a, b) (a = min(a, b))

using namespace std;
const int N = 1 << 18;
typedef long long ll;
int n, a[N], fa[N], sz[N], vis[N];
vector <int> nds[N];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int main() {
    cin >> n;
    ll as = 0;
    rep(i, 1, n) {
        scanf("%d", &a[i]), as -= a[i];
        nds[a[i]].push_back(i);
    }
    nds[0].push_back(0);
    rep(i, 0, n) fa[i] = i, sz[i] = 1;
    per(S, N - 1, 1) for(int T = S; T > S / 2; --T &= S) {
        if(nds[T].empty() || nds[S ^ T].empty()) continue;
        auto mrg = [&](int u, int v) {
            u = find(u), v = find(v);
            if(u == v) return;
            if(sz[u] < sz[v]) swap(u, v);
            fa[v] = u, sz[u] += sz[v];
            as += S;
            if(sz[u] == n + 1) cout << as, exit(0);
        };
        mrg(nds[T][0], nds[S ^ T][0]);
        if(!vis[T]) for(int u : nds[T]) mrg(u, nds[S ^ T][0]);
        if(!vis[S ^ T]) for(int v : nds[S ^ T]) mrg(nds[T][0], v);
        vis[T] = vis[S ^ T] = 1;
    }
    puts("0");
    return 0;
}