2115: [Wc2011] Xor

Time Limit: 10 Sec  

Memory Limit: 259 MB

Submit: 2059  

Solved: 856

[ ][ ][ ]

Description

Input

第一行包括两个整数N和 M， 表示该无向图中点的数目与边的数目。

接下来M 行描写叙述 M 条边，每行三个整数Si。Ti ，Di，表示 Si 与Ti之间存在 一条权值为 Di的无向边。 图中可能有重边或自环。

Output

仅包括一个整数，表示最大的XOR和（十进制结果）,注意输出后加换行回车。

Sample Input

5 7
1 2 2
1 3 2
2 4 1
2 5 1
4 5 3
5 3 4
4 3 2

Sample Output

6

HINT

贪心+线性基(什么是线性基...我仅仅知道宋仲基2333)

有一个性质，一个数被异或两次就等于0。所以一条边在路径中出现偶数次就会被抵消。那么我们就能够随便找一条1到n的路径，然后把它异或一些简单环，就能够得到其它路径。

如今我们要找出无向图中的全部简单环，DFS的过程中加一些推断就能够了。

于是问题就变成从一个数组中找几个数。让他们和还有一个数的异或和最大。方法是对于这个数组求线性基。然后在线性基里倒着贪心。(详见代码)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define F(i,j,n) for(int i=j;i<=n;i++)#define D(i,j,n) for(int i=j;i>=n;i--)#define ll long long#define maxn 50005#define maxm 200005using namespace std;int n,m,cnt,tot,head[maxn];ll ans,d[maxn],a[maxm],b[100];bool vst[maxn];struct edge_type{int next,to;ll w;}e[maxm];inline ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void add_edge(int x,int y,ll w){ e[++cnt]=(edge_type){head[x],y,w};head[x]=cnt; e[++cnt]=(edge_type){head[y],x,w};head[y]=cnt;}inline void dfs(int x){ vst[x]=true; for(int i=head[x];i;i=e[i].next) { int y=e[i].to; if (!vst[y]) { d[y]=d[x]^e[i].w; dfs(y); } else a[++tot]=d[x]^d[y]^e[i].w; }}int main(){ n=read();m=read(); F(i,1,m) { int x=read(),y=read();ll z=read(); add_edge(x,y,z); } dfs(1); ans=d[n]; F(i,1,tot) D(j,63,0) if ((a[i]>>j)&1) { if (!b[j]){b[j]=a[i];break;} else a[i]^=b[j]; } D(i,63,0) if (b[i]&&((ans>>i)&1)==0) ans^=b[i]; printf("%lld\n",ans); return 0;}