Easy Win[gym102331E]

发表于 分类于 ，

题目链接

链接

题意

$m$ 条边，有边权 $a$ 和价值 $v$。在前 $i$ 条边中选出若干条，使得不存在一个环，边权的异或和为 $0$。求选的边的价值之和的最大值。

$n\leq 64,a_i< 2^{60},v_i\leq 10^9$

题解

边权的异或和不为 $0$，可以看成是这些向量都线性无关。

但现在加多了一个环的条件。发现 $n$ 非常小，可以从中搞些事情。

对于一条边 $(x,y,a)$，我们只需要把边权改为 $a+2^{60}(2^x+2^y)$。

那么成环且异或和为 $0$ 的条件就变为了这些边权形成的向量线性相关。

题目转换成，求在前 $i$ 个向量里，选出一些使得它们线性无关，且向量的权值和最大。

如果不是求前缀，则可以排个序，然后从大到小插入线性基里。

现在可以对于线性基里的每个数，记录它是由哪些向量异或得来的。

加入一个向量，如果最后无法插入线性基里，变成了 $0$，则替换掉表示这个向量的所有向量中，权值最小的那个，然后更新由哪些向量得来的数组即可。

时间复杂度 $O(q\frac{(n+60)^2}{w})$。

程序

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline ll read()
{
	ll x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int M=128;
#define Bit bitset<M>
ll ans;
Bit b[M],a[M];
bool vis[M];
ll val[M];
inline void ins(Bit u,ll v)
{
	Bit now; now.reset();
	fd(i,125,0)
		if(u[i])
		{
			if(!vis[i])
			{
				vis[i]=1; ans+=v; val[i]=v;
				b[i]=u; a[i]=now;
				a[i][i]=1;
				return;
			}
			u^=b[i]; now^=a[i];
		}
	int t=-1;
	fo(i,0,125)
		if(vis[i]&&now[i])
			if(t==-1||val[i]<val[t]) t=i;
	if(v>val[t])
	{
		ans+=v-val[t];
		now[t]=0; val[t]=v;
		fo(i,0,125) if(vis[i]&&a[i][t]) a[i]^=now;
	}
}

int main()
{
	read();
	Bit b;
	int x,y,v;
	ll a;
	CASET
	{
		x=read()-1,y=read()-1; a=read(); v=read();
		b.reset();
		b[x]=1; b[y]=1;
		ff(i,0,60) if((a>>i)&1) b[64+i]=1;
		ins(b,v);
		printf("%lld\n",ans);
	}
	return 0;
}