G67 线性基+贪心法 P4151 [WC2011] 最大XOR和路径

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10,B=60;
vector<pair<int,LL>>G[N];
LL p[B+1],d[N];
void ins(LL v)
{
    for(int i=B;i>=0;i--)if((v>>i)&1)
	{
        if(!p[i]){p[i]=v;return ;}
        else v^=p[i];
    }
}
bool v[N];
void dfs(int x)
{
    v[x]=1;
    for(auto i:G[x])
	{
        int y=i.first;LL w=i.second;
		if(!v[y])d[y]=d[x]^w,dfs(y);
        else ins(d[y]^d[x]^w);
    }
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;++i)
	{
        LL c;scanf("%d%d%lld",&x,&y,&c);
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
    memset(v,0,sizeof(v));memset(p,0,sizeof(p));
    dfs(1);
    LL ans=d[n];
    for(int i=B;i>=0;i--)ans=max(ans,ans^p[i]);
    printf("%lld",ans);
    return 0;
}