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

题目描述

输入

第一行包含两个整数N和 M，表示该无向图中点的数目与边的数目。接下来M 行描述 M 条边，每行三个整数Si，Ti ，Di，表示 Si 与Ti之间存在一条权值为 Di的无向边。图中可能有重边或自环。

输出

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

样例输入

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

样例输出

题解

DFS树+高斯消元求线性基

首先肯定能够想到，1->n的路径一定是一条链+选择经过某些环。

那么我们只需要处理出链和环的异或和就可以了。

我们使用DFS树预处理，这样每一条返祖边就对应着一个环。

求出所有环以后，要求最大值，我们需要先对环的异或值求一下线性基，然后再贪心处理即可。

#include <cstdio>

#include <algorithm>

#define N 50010

#define M 200010

using namespace std;

typedef long long ll;

int head[N] , to[M] , tag[M] , next[M] , cnt = 1 , vis[N] , deep[N] , num;

ll len[M] , dis[N] , a[M];

void add(int x , int y , ll z)

{

	to[++cnt] = y , len[cnt] = z , next[cnt] = head[x] , head[x] = cnt;

}

void dfs(int x)

{

	int i;

	vis[x] = 1;

	for(i = head[x] ; i ; i = next[i])

		if(!vis[to[i]])

			dis[to[i]] = dis[x] ^ len[i] , deep[to[i]] = deep[x] + 1 , tag[i] = tag[i ^ 1] = 1 , dfs(to[i]);

}

int main()

{

	int n , m , i , j , x , y , tot = 0;

	ll d , z , ans;

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

	for(i = 1 ; i <= m ; i ++ ) scanf("%d%d%lld" , &x , &y , &z) , add(x , y , z) , add(y , x , z);

	dfs(1);

	for(x = 1 ; x <= n ; x ++ )

		for(i = head[x] ; i ; i = next[i])

			if(!tag[i] && deep[to[i]] < deep[x])

				a[++num] = dis[to[i]] ^ dis[x] ^ len[i];

	for(d = 1ll << 62 ; d ; d >>= 1)

	{

		for(j = ++tot ; j <= num ; j ++ )

		{

			if(a[j] & d)

			{

				swap(a[j] , a[tot]);

				break;

			}

		}

		if(j > num)

		{

			tot -- ;

			continue;

		}

		for(j = 1 ; j <= num ; j ++ )

			if(j != tot && a[j] & d)

				a[j] ^= a[tot];

	}

	ans = dis[n];

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

		if((ans ^ a[i]) > ans)

			ans ^= a[i];

	printf("%lld\n" , ans);

	return 0;

}

巴特西

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

最新文章

热门文章