【BZOJ2115】[Wc2011] Xor

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

HINT

题解：以前用到DFS树的情况比较少，现在需要在加深一下对DFS树的理解了~

*结论：任意一条从1到n的路径，都可以被任意令一条从1到n的路径和一堆环替代。（因为是异或，所以显然）

所以我们只需要任意找一条从1到n的路径，然后再把所有的环都找出来。

但是我们这里的环不是Tarjan那里的环，我们要找到的都是简单环，所以要用DFS（有什么区别？）

因为DFS树（就是DFS找出的树）有一个性质：没有横叉边，所以每条返祖边都唯一对应一个简单环。

那么现在问题就变成了给出一堆数，可以选或不选，要求选出来的数和一个固定的数的异或和最大。

方法：网上大部分题解都说先搞出线性基，然后贪心就行了，然而本蒟蒻不知道什么是线性基，现去学了一发

高斯消元的过程，就是我们将一个满秩的矩阵尽可能的消成一个上三角矩阵的过程，而我对线性基的理解就是：最后得到的那个近似于上三角的矩阵（因为有的位置可能没有消完）。容易发现，线性基可以表示原集合中的所有数。

所以你已经知道了一个上三角矩阵，然后如何使得异或值最大呢？显然从大到小一个一个试就行了嘛！如果当前位线性基不为0，但是原数为0，那就异或上这个数就行了。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

int n,m,cnt,tot;

int to[200010],next[200010],head[50010],vis[50010];

ll val[200010],v[500010],dis[50010],ans;

void add(int a,int b,ll c)

{

	to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;

}

void dfs(int x,int fa)

{

	vis[x]=1;

	for(int i=head[x];i!=-1;i=next[i])

	{

		if(to[i]==fa)	continue;

		if(vis[to[i]])	v[++tot]=val[i]^dis[to[i]]^dis[x];

		else	dis[to[i]]=dis[x]^val[i],dfs(to[i],x);

	}

}

void gauss()

{

	ll i;

	int j,k=0;

	for(i=1ll<<60;i;i>>=1)

	{

		for(k++,j=k;j<=tot;j++)	if(v[j]&i)

		{

			swap(v[j],v[k]);

			break;

		}

		if(!(v[k]&i))

		{k--;	continue;}

		for(j=k+1;j<=tot;j++)	if(v[j]&i)	v[j]^=v[k];

	}

}

int main()

{

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

	int i,a,b;

	ll c;

	memset(head,-1,sizeof(head));

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

	{

		scanf("%d%d%lld",&a,&b,&c);

		add(a,b,c),add(b,a,c);

	}

	dfs(1,0),gauss();

	ans=dis[n];

	for(i=1;i<=60&&i<=tot;i++)	if((ans^v[i])>ans)	ans^=v[i];

	printf("%lld",ans);

	return 0;

}

巴特西

【BZOJ2115】[Wc2011] Xor 高斯消元求线性基+DFS