【线性基】【贪心】【独立环】bzoj2115 [Wc2011] Xor

网上到处都是题解，自己画个图也很好理解。虽然环的个数很多，但是都可以通过独立环之间异或出来，不用管。

独立环求法：生成树之后，每次向图里添加非树边(u,v)，则这个独立环的异或和为sum[u]^sum[v]^w(u,v)。sum[u]为从1到u的任意一条路径的异或和。

#include<cstdio>

using namespace std;

#define N 50001

#define M 100001

typedef long long ll;

ll w[M<<1],sum[N],a[M],base[64],zs[M];

int n,m,v[M<<1],first[N],en,next[M<<1],xs[M],ys[M];

bool vis[N],used[M];

int e2;

void AddEdge(int U,int V,ll W)

{

	v[++en]=V;

	w[en]=W;

	next[en]=first[U];

	first[U]=en;

}

void dfs(int U)

{

	vis[U]=1;

	for(int i=first[U];i;i=next[i])

	  if(!vis[v[i]])

	    {

	      sum[v[i]]=(sum[U]^w[i]);

	      dfs(v[i]);

	    }

}

int fa[N],rank[N];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void Union(int U,int V)

{

	if(rank[U]<rank[V]) fa[U]=V;

	else

	  {

	  	fa[V]=U;

	  	if(rank[U]==rank[V])

	  	  ++rank[U];

	  }

}

int main()

{

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

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

	  {

	  	scanf("%d%d%lld",&xs[i],&ys[i],&zs[i]);

	  	AddEdge(xs[i],ys[i],zs[i]);

	  	AddEdge(ys[i],xs[i],zs[i]);

	  }

	dfs(1);

	for(int i=1;i<=n;++i) fa[i]=i;

	int cnt=0;

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

	  {

	  	int f1=find(xs[i]),f2=find(ys[i]);

	  	if(f1!=f2)

	  	  {

	  	  	++cnt;

	  	  	used[i]=1;

	  	  	Union(f1,f2);

	  	  	if(cnt==n-1)

	  	  	  break;

	  	  }

	  }

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

	  if(!used[i])

	    a[++e2]=(sum[xs[i]]^sum[ys[i]]^zs[i]);

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

	  for(int j=63;j>=0;--j)

	    if((a[i]>>j)&1)

	      {

	      	if(!base[j])

	      	  {

	      	  	base[j]=a[i];

	      	  	break;

	      	  }

	      	a[i]^=base[j];

	      }

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

	  if((sum[n]^base[i])>sum[n])

	    sum[n]^=base[i];

	printf("%lld\n",sum[n]);

	return 0;

}