BZOJ2115: [Wc2011] Xor【线性基】

2115: [Wc2011] Xor

【题目描述】

传送门

【题解】

将图拆成环和链。链就可以看成,一条1到n的路径,如果路径和环没有相交,那么就可以看成走一段路之后绕一个环然后走回来就可以了。所以最后就直接找1到n路径异或一个环的最大值就可以了。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=50005,MAXE=100005;
typedef long long LL;
int n,m;LL v[65],Sum[MAXN];bool vis[MAXN];
struct Edge{
    int tot,lnk[MAXN],son[MAXE<<1],nxt[MAXE<<1];LL W[MAXE<<1];
    void Add(int x,int y,LL w){son[++tot]=y;W[tot]=w;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
void Insert(LL val){
    for(int i=62;i>=0;--i)
    if((1ll<<i)&val){
        if(!v[i]){v[i]=val;break;}
        val^=v[i];
    }
}
LL Query_Max(LL x){
    LL ret=x;
    for(int i=62;i>=0;--i)
    ret=max(ret,ret^v[i]);
    return ret;
}
void DFS(int x){
    vis[x]=1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(vis[E.son[j]]) Insert(Sum[x]^Sum[E.son[j]]^E.W[j]);
    else Sum[E.son[j]]=Sum[x]^E.W[j],DFS(E.son[j]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;LL w;scanf("%d%d%lld",&x,&y,&w);
        E.Add(x,y,w),E.Add(y,x,w);
    }
    DFS(1);
    printf("%lld\n",Query_Max(Sum[n]));
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部