[EZOI][1211NOI模拟赛]Xor(线性基)

§ 1 题意

给定简单无向连通带权图 $G=\lt V,E\gt$,其中对于 $u \in V$ 有点权 $W_u$,对于 $(i,j) \in E$ 有边权 $w_{i,j}$。

定义边集 $E$ 的权值为 $\bigoplus\limits_{(i,j) \in E} w_{i,j}$。

若一个割 $C$ 将图 $G$ 的点集 $V$ 分成 $S,T$ 两部分,其中 $S \cup T=V$,则简记为 $C=\lt S,T\gt$。

定义一个割 $C$ 是合法的,当且仅当对于 $\forall S’ \subseteq S,S’ \neq \emptyset$,割边集 $C’=\lt S’,T’\gt(T’=V-S’)$ 的权值均非 $0$。

求合法割集中 $\sum\limits_{u \in S}W_u-\sum\limits_{u \in T}W_u$ 的最大值。

$n \leq 10^5,m \leq 2*10^5,W_u \leq 10^{12},w_{i,j} \lt 2^{63}$。


§ 2 分析

边 $(i,j)$ 在割集 $C=\lt S,T\gt$ 中,当且仅当它的一个端点在 $S$ 中,另一个在 $T$ 中。此时割集权值要异或 $w_{i,j}$。

如果边 $(i,j)$ 的两个端点均在 $S$ 中,可以视作割集权值异或两次 $w_{i,j}$,等价于没有贡献。

记点 $u$ 所有出边的边权异或和 $f_u=\bigoplus\limits_{(u,i) \in E} w_{u,i}$,则割 $C=\lt S,T\gt$ 的权值为 $\bigoplus\limits_{u \in S}f_u$。

由于合法割集需要满足不存在 $S’ \subseteq S,S’ \neq \emptyset$ 使得割 $C’=\lt S’,V-S’\gt$ 权值为 $0$,所以 $S$ 中的点的 $f_u$ 要线性无关,使用线性基按 $W_u$ 从大到小贪心即可。

总时间复杂度为 $O(n\log w)$。


§ 3 代码

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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

template <typename T> inline void getint(T &num){
register int ch, neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}

int n, m; ll bas[63], tot = 0, ans = 0;
struct Node {ll w, f;} p[100005];

inline bool operator < (const Node &p1, const Node &p2) {return p1.w > p2.w;}

inline int ins(ll val){
for(register int i = 62; ~i; i--) if(val & (1LL << i))
if(bas[i]) val ^= bas[i]; else return bas[i] = val, 1;
return 0;
}

int main(){
getint(n), getint(m);
for(register int i = 1; i <= n; i++) getint(p[i].w), tot += p[i].w;
for(register int i = 1; i <= m; i++){
int u, v; ll w; getint(u), getint(v), getint(w);
p[u].f ^= w, p[v].f ^= w;
}
sort(p + 1, p + n + 1);
for(register int i = 1; i <= n; i++) if(ins(p[i].f)) ans += p[i].w;
printf("%lld\n", ans * 2 - tot);
return 0;
}