Accepted/11364K/888MS

bzoj2115.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
const int maxn=50005;
vector <pair<int,long long> > e[maxn];
vector <long long> ring;
typedef vector<pair<int,long long> >::iterator pii;
int num;
int n,m,tu,tv;
long long tc;
long long d[maxn];
int vis[maxn];
void dfs(int x)
{
    vis[x]=1;
    for (pii i=e[x].begin();i!=e[x].end();i++)
    {
        if (!vis[i->first])
        {
            d[i->first]=d[x]^i->second;
            dfs(i->first);
        }else
        {
            ring.push_back(d[x]^d[i->first]^i->second);
        }
    }
}
int gauss()
{
    num=ring.size();
    int k=1;
    for (int p=63;~p;p--)
    {
        int t=-1;
        for (int j=k;j<num;j++)
        {
            if ((ring[j]>>p)&1)
            {
                t=j;
                break;
            }
        }
        if (~t)
        {
            swap(ring[t],ring[k]);
            for (int j=1;j<num;j++)
                if (j!=k && ((ring[j]>>p)&1))
                    ring[j]^=ring[k];
            k++;
        }
    }
    return k-1;
}
int main()
{
    ring.push_back(0);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&tu,&tv,&tc);
        e[tu].push_back(make_pair(tv,tc));
        e[tv].push_back(make_pair(tu,tc));
    }
    dfs(1);
    int cnt=gauss();
    long long ans=d[n];
    for (int i=1;i<=cnt;i++)
        ans=max(ans,ans^ring[i]);
    printf("%lld\n",ans);
    return 0;
}