- 1#include
- 2
- 3typedeflong long lnt;
- 4
- 5 const intmxn =500005;
- 6
- 7 int n, m;
- 8
- 9 int hd[mxn];
- 10 int to[mxn];
- 11 int nt[mxn];
- 12 lnt vl[mxn];
- 13
- 14inlinevoidaddEdge(intu,int v, lnt w)
- 15 {
- 16 static inttot =0;
- 17
- 18nt[tot] = hd[u];
- 19to[tot] = v;
- 20vl[tot] = w;
- 21hd[u] = tot++;
- 22 }
- 23
- 24 int vis[mxn];
- 25 lnt dis[mxn];
- 26 lnt cir[mxn];
- 27 int tot;
- 28
- 29 voiddfs(int u)
- 30 {
- 31vis[u] =true;
- 32
- 33 for(inti = hd[u], v; ~i; i = nt[i])
- 34 if(!vis[v = to[i]])
- 35dis[v] = dis[u] ^ vl[i], dfs(v);
- 36 else
- 37cir[++tot] = dis[u] ^ dis[v] ^ vl[i];
- 38 }
- 39
- 40 int cnt;
- 41
- 42inlinevoidgauss(void)
- 43 {
- 44 for(inti =1; i <= tot; ++i)
- 45 {
- 46 for(intj = tot; j > i; --j)
- 47 if(cir[i] < cir[j])
- 48 std::swap(cir[i], cir[j]);
- 49
- 50 if (cir[i])
- 51++cnt;
- 52 else
- 53 break;
- 54
- 55 for(intj =63; ~j; --j)
- 56 if((cir[i] >> j) &1)
- 57 {
- 58 for(intk =1; k <= tot; ++k)
- 59 if(i != k && (cir[k] >> j) &1)
- 60cir[k] ^= cir[i];
- 61
- 62 break;
- 63 }
- 64 }
- 65 }
- 66
- 67inlinevoidsolve(void)
- 68 {
- 69lnt ans = dis[n];
- 70
- 71 for(inti =1; i <= cnt; ++i)
- 72ans = std::max(ans, ans ^ cir[i]);
- 73
- 74printf("%lld\n", ans);
- 75 }
- 76
- 77signed main(void)
- 78 {
- 79scanf("%d%d", &n, &m);
- 80
- 81memset(hd, -1,sizeof(hd));
- 82
- 83 for(inti =1; i <= m; ++i)
- 84 {
- 85 static int x, y;
- 86 static lnt w;
- 87
- 88scanf("%d%d%lld", &x, &y, &w);
- 89
- 90 addEdge(x, y, w);
- 91 addEdge(y, x, w);
- 92 }
- 93
- 94dfs(1);
- 95
- 96 gauss();
- 97
- 98 solve();
- 99}
来源: