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("");
    }
}