bzoj 2115: [Wc2011] Xor

神题%%%

可以证明的是从1到n的路径是由一条路上挂着几个环构成的。

求出所有的环，线性基，最大，完了。

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 inline LL ra()
 7 {
 8     LL x=0,f=1; char ch=getchar();
 9     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
10     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
11     return x*f;
12 }
13 struct node{int to,next; LL v;}e[N<<2];
14 bool vis[N];
15 LL p[105],A[N<<2],dis[N];
16 int cnt,head[N],sz,n,m;
17 void insert(int x, int y, LL v)
18 {
19     e[++cnt].to=y; e[cnt].next=head[x]; e[cnt].v=v; head[x]=cnt;
20 }
21 void dfs(int x, LL s)
22 {
23     vis[x]=1; dis[x]=s;
24     for (int i=head[x];i;i=e[i].next)
25     {
26         if (vis[e[i].to]) A[++sz]=e[i].v^s^dis[e[i].to];
27         else dfs(e[i].to,s^e[i].v);
28     }
29 }
30 void guass()
31 {
32     for (int i=1; i<=sz; i++)
33     {
34         for (int j=62; j>=0; j--)
35             if ((1LL<<j)&A[i])
36             {
37                 if (!p[j]) {p[j]=A[i]; break;}
38                 else A[i]^=p[j];
39             }
40     }
41 }
42 int main()
43 {
44     n=ra(); m=ra();
45     for (int i=1; i<=m; i++) 
46     {
47         int x=(int)ra(),y=(int)ra(); LL v=ra();
48         insert(x,y,v); insert(y,x,v);
49     }
50     dfs(1,0);
51     guass();
52     LL ans=dis[n];
53     for (int i=62; i>=0; i--) ans=max(ans,ans^p[i]);
54     cout<<ans<<endl;
55     return 0;
56 }