menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维+线性基]BZOJ2115(Wc2011)【Xor】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

给出一张有边权的无向图,求从 $1$ 到 $n$ 路径异或最大值,可以重复走点并且可以重复经过 $n$ 。

解题报告

好妙的题!无向图中的环是可以经过也可以不经过的,所以我们可以把所有环加入线性基。那么现在的问题就是如何选取环使得异或和最大,可以想到枚举一条路径并把路径上能够经过的环加入线性基,然后用线性基就可以求出这条路径的最大值。

然而复杂度飞天了,怎么办呢?我们发现如果如果有多条路径都能从 $1$ 到 $n$ ,那么就形成了若干个环,所以干脆随便选出一条 $1$ 到 $n$ 的路径,做全图环的线性基就行啦。

但是这样有个问题,可能会出现路径和环不交的情况!实际上因为可以重复走,所以可以强行走到环再走回来……异或和不变。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=50000,maxm=200000,Log=60;

int n,m;LL sum[maxn+5],M[Log+5],ans;bool vis[maxn+5];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5];LL w[maxm+5];

#define Add(x,y,z) (son[E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E++)
inline void Insert(LL x) {for (int j=Log;~j;j--) if (x>>j&1) if (!M[j]) {M[j]=x;break;} else x^=M[j];}
void Dfs(int x,int pre=-1){
    for (int j=(vis[x]=true,lnk[x]);~j;j=nxt[j])
        if (j^1!=pre) if (vis[son[j]]) Insert(sum[x]^sum[son[j]]^w[j]);
        else if (!vis[son[j]]) sum[son[j]]=sum[x]^w[j],Dfs(son[j],j);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=m;i++) {int x,y;LL z;scanf("%d%d%lld",&x,&y,&z),Add(x,y,z),Add(y,x,z);}
    Dfs(1);ans=sum[n];for (int j=Log;~j;j--) if ((ans^M[j])>ans) ans^=M[j];printf("%lld\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up