Kuroni and Antihype | Codeforces 1305G

题目链接

一张有 \(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;
}