JZOJ 5059.最大割

考虑把每个点的点权定义为与它相连的所有边的边权的异或和,那么就变成了一个带修改线性基模板题(

如何操作?对向量空间里所有向量维护其被基中哪些向量表出,修改时从被其表出的向量中取最高位最低的一个,用它来还原其他被这个向量表出的向量。
然后异或之后重新加入基中。

代码:

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
#include <cstdio>
#include <bitset>
#include <cstring>
using namespace std;
const int N = 500;
const int L = 1e3;
int n,m,len;
int bas[L + 5];
bitset<L + 5> a[N + 5],c[N + 5],w,ans;
char s[L + 5];
void insert(int x)
{
for(register int i = len;~i;--i)
if(a[x][i])
{
if(bas[i])
a[x] ^= a[bas[i]],c[x] ^= c[bas[i]];
else
{
bas[i] = x;
break;
}
}
}
void update(int x)
{
int min = 0;
for(register int i = 1;i <= n;++i)
if(c[i][x] && a[i].none())
{
min = i;
break;
}
if(!min)
for(register int i = 0;i <= len;++i)
if(c[bas[i]][x])
{
min = bas[i],bas[i] = 0;
break;
}
for(register int i = 1;i <= n;++i)
if(c[i][x] && (i ^ min))
a[i] ^= a[min],c[i] ^= c[min];
a[min] ^= w,insert(min);
}
bitset<L + 5> query()
{
bitset<L + 5> ret;
ret.reset();
for(register int i = len;~i;--i)
if(!ret[i] && bas[i])
ret ^= a[bas[i]];
return ret;
}
int main()
{
freopen("cut.in","r",stdin),freopen("cut.out","w",stdout);
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
c[i][i] = 1;
for(int u,v,l,flag;m;--m)
{
scanf("%d%d%s",&u,&v,s),len = max(len,l = strlen(s) - 1),w.reset();
for(register int i = 0;i <= l;++i)
w[i] = s[l - i] ^ '0';
update(u),update(v),ans = query(),flag = 0;
for(register int i = len;~i;--i)
ans[i] && (flag |= 1),
flag && putchar((bool)ans[i] + '0');
!flag && putchar('0'),puts("");
}
}