Description：

给一个无向图，求 $1$ 到 $N$ 边权异或和最大的路径。

$1 \le N \le 50000$

Solution：

先随便选一条路径，然后把所有的环找出来，发现每一条 $1$ 到 $N$ 的路径都可以由某条路径套上一些环得到，如果路径与环有相交部分，那么相交部分走了两次，如果没有相交部分，可以看成沿一条路径去，绕一个环再原路返回，走两次对答案无贡献，用 $dfs$ 找环，用线性基维护异或最大值，最后查询包含原先选定路径情况下的异或最大值。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define MAXM 100010

typedef long long ll;

struct edge

{

    int to,nxt;

    ll v;	

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,ll c)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    ++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

    return;	

}

struct LinearBase

{

    static const int BASE = 63;

    ll d[BASE + 1];

    LinearBase(){memset(d,0,sizeof(d));}

    void insert(ll k)

    {

        for(int i = BASE;i >= 0;--i)

        {

            if(k & (1ll << i))

            {

                if(d[i] == 0)

                {

                    d[i] = k;

                    break;	

                }

                else

                {

                    k ^= d[i];	

                }

            }

        }

        return;

    }

    ll query_max(ll st)

    {

        for(int i = BASE;i >= 0;--i)

        {

            if((st ^ d[i]) > st)

            {

                st ^= d[i];	

            }

        }

        return st;

    }	

}s;

bool v[MAXN];

ll val[MAXN];

void dfs(int k)

{

    v[k] = true;

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(!v[e[i].to])

        {

            val[e[i].to] = val[k] ^ e[i].v;

            dfs(e[i].to);

        }

        else

        {

            s.insert(val[k] ^ val[e[i].to] ^ e[i].v);	

        }

    }

    return;	

}

int main()

{

    scanf("%d%d",&n,&m);

    int a,b;

    ll c;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d%d%lld",&a,&b,&c);

        add(a,b,c);	

    }

    dfs(1);

    cout << s.query_max(val[n]) << endl;

    return 0;    

}