头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Bzoj 2115

描述:

$一个无向图,可能有自环与重边,选择一条从1到n的路径, \\
每个点和边都可以重复经过,使边权异或和最大。$


思路:

$找出所有环,简单证明一下,先任意找一条路径,再找到环, \\
如果环不在路径上,路径到环的这段距离会被走两次,异或 \\
以后对答案不产生贡献,再证路径的任意性,如果存在一条 \\
更优路径,更优路径与当前路径必然形成环,该环与当前选 \\
择的路径进行异或即可得到更优路径。异或之和最大,即求 \\
环的异或的线性基。在dfs过程中求环的异或时预处理一个 \\
sz数组,sz[i]代表从1到i路径上的边权异或和$


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
/**************************************************************
Problem: 2115
User: Decaku
Language: C++
Result: Accepted
Time:892 ms
Memory:17572 kb
****************************************************************/

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=5e4+5;
const ll maxm=5e5+5;
vector<pair<ll,ll> >g[maxn];
ll n,m;
ll vis[maxn],Xor[maxm],sz[maxm],cnt;
ll p[65];

void dfs2(ll s,ll f)
{
vis[s]=1;
//for(ll i=g[s].size()-1;i>=0;i--)
for(ll i=0; i<=g[s].size()-1; i++)
{
ll v=g[s][i].first,w=g[s][i].second;
if(v==f)
continue;
if(vis[v])
{
Xor[++cnt]=(sz[s]^sz[v]^w);
continue;
}
else
{
sz[v]=(sz[s]^w);
dfs2(v,s);
}
}
}

int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=1; i<=m; i++)
{
ll u,v,w;
scanf("%lld %lld %lld",&u,&v,&w);
g[u].push_back(make_pair(v,w));
g[v].push_back(make_pair(u,w));
}
memset(vis,0,sizeof(vis));
dfs2(1,0);

for(int i=1; i<=cnt; i++)
{
for(int j=62; j>=0; j--)
{
if(!(Xor[i]>>j))
continue;
if(!(p[j]))
{
p[j]=Xor[i];
break;
}
else
Xor[i]^=p[j];
}
}
ll ans=sz[n];

for(int i=62; i>=0; i--)
{
if((ans^p[i])>ans)
ans^=p[i];
}
printf("%lld\n",ans);
}
avatar Decaku 如果人生的路有很长,愿你的荣耀永不退场。