目录
显示
题目链接
https://www.luogu.com.cn/problem/P4151
题解
一条边经过两次后,这条边就对答案没有贡献了。
但是通过这条边,我们可以到达某些新边,从而将新边的答案计入贡献中。
比如一条边连着一个环的情况,在这种情况下,如果我们经过了这个环,连接这个环的边不会对答案产生贡献,但是这个环的贡献算入了答案中。
这样我们有了一种思路:将答案分为两部分,一部分是 \(1 \to n\) 的路径,另一部分是我们可以到达的环。在包含 \(1 \to n\) 的路径的贡献前提下,我们求的是环的子集与链的最大异或和。
从 \(1 \to n\) 的路径有很多条,选哪一条链呢?事实上随便选一条就可以。
原因是:从 \(1 \to n\) 的若干条路径也组成了环,如果我们选了一条路径,后面发现另外一条路径更优的话,我们只需选包含这两条路径的环,从而将原来路径的贡献消去,变成新路径的贡献。
#include <iostream> using namespace std; struct edge { int v,next; long long w; }e[200005]; int head[50005],vis[50005],cnt; long long res[50005],p[65]; void add(long long x) { for(int i=63;i>=0;i--) if((x>>i)&1) { if(!p[i]) { p[i]=x; return; } else x^=p[i]; } } long long query(long long x) { for(int i=63;i>=0;i--) if((x^p[i])>x)x^=p[i]; return x; } void addedge(int u,int v,long long w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } void dfs(int u,long long w) { vis[u]=1; res[u]=w; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(vis[v])add(w^e[i].w^res[v]); else dfs(v,w^e[i].w); } } int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) { int u,v; long long w; cin>>u>>v>>w; addedge(u,v,w); addedge(v,u,w); } dfs(1,0); cout<<query(res[n])<<endl; return 0; }