bzoj - 2115

Posted by WildCow on June 6, 2018

[Wc2011] Xor

Time Limit: 10MS
Memory Limit: 259 MB

Description

avater

Input

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

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


首先很显然能够发现
由于异或的性质
对于一条路径我们反复的走是没有意义的
因此最终答案路径一定是由许多的环和一条从1 到 n 的单链路径组成

我们有一个构造方法
处理出任意一个从 1 到 n 的单链路径的异或
再 dfs 处理出所有的环的异或
然后我们求出这些异或值的线性基
再取 max 就是答案

接下来证明正确性
如果答案包含的环不在答案包含的单链路径上
那么我们可以走到这个环之后绕环一周之后原路返回
可以发现到达这个环的路径被走了两次于是被抵消
因此我们没必要处理到达这个环的路径
且任意一个环对答案的贡献只是这个环的异或值

对于 1 到 n 的多条路径
假设我们随便取一个单链路径不是答案所包含的单链路径
那么显然随便选取的单链路径和答案包含的单链路径构成了一个环
这个环的异或值也会被纳入线性基中
那么随便选取的单链路径的异或再异或上那个环的异或
能得到最终答案的单链路径

这样问题就解决了
不过最后取最大值时应该倒序遍历线性基


#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200010;

struct Node
{
	int to;
	int ne;
	LL w;
};

Node node[N];
int head[N];
int top;
int n, m;
LL dis[N];
LL ma[N];
LL mb[N];
int vis[N];
int cnt;

void ini()
{
	top = 0;
	memset(head, -1, sizeof(head));
}

void Add_edge(int from, int to, LL w)
{
	node[top].to = to;
	node[top].w = w;
	node[top].ne = head[from];
	head[from] = top;
	top ++;
}

void Dfs(int u, int pre)
{
	for(int i = head[u]; i != -1; i = node[i].ne){
		int v;

		v = node[i].to;
		if(v != pre){
			if(vis[v]){
				ma[cnt] = dis[u] ^ node[i].w ^ dis[v];
				cnt ++;
			}
			else{
				vis[v] = 1;
				dis[v] = dis[u] ^ node[i].w;
				Dfs(v, u);
			}
		}
	}
}

void Gauss()
{
	for(int i = 0; i < cnt; i ++){
		for(int j = 62; j >= 0; j --){
			if((ma[i] >> j) & 1){
                if(!mb[j]){
                    mb[j] = ma[i];
                    break;
                }
                else{
                    ma[i] ^= mb[j];
                }
            }
		}
	}
}

int main(int argc, char const *argv[])
{
	LL ans;

	while(scanf("%d%d", &n, &m) == 2){
		ini();
		memset(vis, 0, sizeof(vis));
		memset(ma, 0, sizeof(ma));
		memset(dis, 0, sizeof(dis));
		cnt = 0;
		for(int i = 0; i < m; i ++){
			int u, v;
			LL w;

			scanf("%d%d%lld", &u, &v, &w);
			Add_edge(u, v, w);
			Add_edge(v, u, w);
		}
		Dfs(1, -1);
//		for(int i = 0; i < cnt; i ++){
//            printf("666 = %lld\n", ma[i]);
//		}
		Gauss();
		ans = dis[n];
		/// cout << ans << endl;
		for(int i = 62; i >= 0; i --){
            /// printf("mb[i] = %d\n", mb[i]);
            /// printf("cnt = %lld   %lld\n", ans ^ mb[i], ans);
			if((ans ^ mb[i]) > ans){
                // printf("be = %lld\n", ans);
				ans = ans ^ mb[i];
				// printf("en = %lld\n", ans);
			}
		}
		printf("%lld\n", ans);
	}

	return 0;
}