「BZOJ-2115」[Wc2011] Xor (线性基)

发表于 | 分类于 ，

BZOJ3732-[Wc2011] Xor
给定一个无向图，求节点1到结点N的XOR和最大路径，一条边可以重复经过多次。

解法

由于路径可以重复经过，对于图上的任意一个环，可以选择取或不取该环的值，而对于点1-n的路径异或和最大值，可以视为某一条1-n的路径，异或上若干个环的路径长度的最大值。

预处理求出图上所有环的异或和，并任取一条1-n的路径异或和，对这些值求线性基，即可求出最大值。

为什么1-n的路径可以任取：假设1-n有大于一条路径，其中另一条路径与所有环异或能取得更优解，那么此时可视为有一个经过1和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
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
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const int maxn=1e5+10;

int head[maxn],cnt=0;
struct Edge {int nex,to; ll w; }edge[20*maxn];

void add_edge(int u,int v,ll w)
{
    edge[cnt].nex=head[u];
    edge[cnt].to=v;
    edge[cnt].w=w;
    head[u]=cnt++;
}

void add(int u,int v,ll w)
{
    add_edge(u,v,w);
    add_edge(v,u,w);
}

ll _xor[maxn],a[5*maxn],tot=0;
bool vis[maxn]={false};

void dfs(int u)
{
    for(int i=head[u];~i;i=edge[i].nex)
    {
        int v=edge[i].to;
        if(!vis[v])
        {
            _xor[v]=_xor[u]^edge[i].w;
            vis[v]=true;
            dfs(v);
        }
        else
        {
            a[tot++]=_xor[u]^_xor[v]^edge[i].w;
            if(!a[tot-1]) tot--;
        }
    }
}

ll b[70];

void cal()
{
    memset(b,0,sizeof b);
    for(int i=0;i<tot;i++)
    {
        for(int j=63;j>=0;j--)
        {
            if(a[i]>>j&1)
            {
                if(b[j]) a[i]^=b[j];
                else
                {
                    b[j]=a[i];
                    for(int k=j-1;k>=0;k--) if(b[k]&&(b[j]>>k&1)) b[j]^=b[k];
                    for(int k=j+1;k<=63;k++) if(b[k]>>j&1) b[k]^=b[j];
                    break;
                }
            }
        }
    }
}

int main()
{
    int n,m,u,v;
    ll w;
    scanf("%d%d",&n,&m);
    memset(head,0xff,sizeof head);
    while(m--)
    {
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);
    }
    _xor[1]=0;
    dfs(1);
    cal();
    ll ans=_xor[n];
    for(int i=63;i>=0;i--) if(ans<(ans^b[i])) ans^=b[i];
    printf("%lld\n",ans);
    return 0;
}