首页 > 其他 > 详细

[WC2011]最大XOR和路径

时间:2019-02-16 19:58:04      阅读:213      评论:0      收藏:0      [点我收藏+]

题目

神仙题啊

发现题目里有一句非常重要的话“当一条边在路径中出现了多次时,其权值在计算 XOR 和时也要被计算相应多的次数

这告诉我们走一条边两次显然没有什么贡献

所以计算贡献的应该是那些走了奇数次的边

我们发现我们可以把一个环上所有的边都走奇数次遍历一个环

而两个环之间如果有路径连接的话这两个环的贡献都可以被算上,而不去计算路径的贡献

也就是连接两个环的路径走一次,环上的边走两次

所以环非常关键,我们可以选择很多的环使得我们的权值异或起来最大

这里就需要一个线性基了,我们可以配合\(dfs\)搜索树,遇到一条返祖边就找到一个环,加入线性基

尽管并没有加入所有的环,但是这些环可以将所有其他环都表示出来了

之后我们选择一条从\(1\)\(n\)的路径作为初值,从线性基里选择一些环来增广这条路径,使得异或和最大就好了

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 100005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline LL read() {
    LL x=0;char c=getchar();while(c<‘0‘||c>‘9‘) c=getchar();
    while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt;LL w;}e[maxn<<1];
int head[maxn],dfn[maxn];
LL pre[maxn];
int num,n,m,cnt;
LL lb[66];
inline void add(int x,int y,LL z) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=z;}
inline void ins(LL x) {
    for(re int j=62;j>=0;--j)
        if(x>>j&1ll) {
            if(!lb[j]) {lb[j]=x;break;}
            else x^=lb[j];
        }
}
void tarjan(int x,int fa) {
    dfn[x]=1;
    for(re int i=head[x];i;i=e[i].nxt)
    if(!dfn[e[i].v]) pre[e[i].v]=pre[x]^e[i].w,tarjan(e[i].v,x);
    else ins(pre[x]^pre[e[i].v]^e[i].w); 
}
int main()
{
    n=read(),m=read();
    int x,y;LL z;
    for(re int i=1;i<=m;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    tarjan(1,0);
    LL ans=pre[n];
    for(re int i=62;i>=0;--i) if((ans^lb[i])>ans) ans^=lb[i];
    printf("%lld\n",ans);
    return 0;
}

[WC2011]最大XOR和路径

原文:https://www.cnblogs.com/asuldb/p/10388772.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!