图论+线性基高斯消元与主元：1019T2 / P4151-Toy模板网

这篇具有很好参考价值的文章主要介绍了图论+线性基高斯消元与主元：1019T2 / P4151。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

http://cplusoj.com/d/senior/p/SS231019B

相当于图上选一条链和一堆环

考虑dfs生成树。

则链是两条从根出发的链

环是每条返祖边组成的环

所以环和链的异或和可以求出来

链的放到线性基里

然后线性基通过高斯消元求主元（贪心思想，主元可以令那一位一定为1。那么就钦定主元为必选，这样一定更优）

高消的过程中也需要对链进行消元

最后用链来查询，丢01trie上维护文章来源地址https://www.toymoban.com/news/detail-718838.html

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int 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<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
//#define mo
int n, m, i, j, k, T;
int ans, C, MY, dis[N]; 
struct line_kun {
	int p[100]; 
	void push(int k) {
//		printf("Add %lld\n", k); 
		for(int j = 62; j >= 0; --j)
			if((k>>j)&1) {
				if(!p[j]) { p[j]=k; break; }
				k^=p[j];  
			}
	}
	void xiaoyuan() {
//		for(int j = 62; j >= 0; --j) printf("%lld ", p[j]); printf("\n"); 
		for(int j = 62; j >= 0; --j)
			if(p[j]) {
				for(int i = 62; i > j; --i) 
					if((p[i]>>j)&1) p[i]^=p[j]; 
				for(int i = 1; i <= n; ++i) 
					if((dis[i]>>j)&1) dis[i]^=p[j]; 
			}
//		for(int j = 62; j >= 0; --j) printf("%lld ", p[j]); printf("\n"); 
	}
	pair<int, int> main_Y() {
		int k = (1ll<<62)-1, ans = 0; 
		for(int j = 62; j >= 0; --j) 
			if(p[j]) k-=(1ll<<j), ans^=p[j]; 
		return {k, ans}; 
	}
}J; 
struct Trie_tree {
	int tot = 1, son[N * 60][2] ; 
	int que_max(int x) {
//		printf("Que_mx : %lld\n", x); 
		int u = 1, i, k, ans=0; 
		for(i = 62; i>=0; --i) {
			k = (x>>i)&1ll; 
			if(son[u][k^1]) u=son[u][k^1], ans|=((k^1)<<i); 
			else u=son[u][k], ans|=(k<<i); 
		}
//		printf("\t We get %lld\n", ans); 
		return ans; 
	}
	void add(int x) {
		int u = 1, i, k; 
		for(i = 62; i >= 0; --i) {
			k = (x>>i)&1ll; 
			if(!son[u][k]) son[u][k] = ++tot; 
			u = son[u][k]; 
		}
	}
}Trie;
struct node {
	int y, z; 
};
int u, v, w; 
pair<int, int>p; 
vector<node>G[N]; 

void dfs(int x, int fa) {
	for(auto t : G[x]) {
		int y = t.y, z = t.z; 
//		if(t.y == fa) continue; 
		if(dis[y] == -1) {
			dis[y] = dis[x] ^ z; 
			dfs(y, x); 
		}
		else J.push(dis[x] ^ dis[y] ^ z); 
	}
}

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	freopen("path.in", "r", stdin);
//	freopen("path.out", "w", stdout);
	T=read();
//	while(T--) {
//
//	}
	n = read(); m = read(); 
	for(i=1; i<=m; ++i) {
		u = read(); v = read(); w = read(); 
		G[u].pb({v, w}); G[v].pb({u, w}); 
	}
	memset(dis, -1, sizeof(dis)); 
	dis[1]=0; dfs(1, 0); 
//	for(i=1; i<=n; ++i) printf("%lld ", dis[i]); printf("\n"); 
	J.xiaoyuan(); 
	p = J.main_Y(); MY = p.first; C = p.second; 
//	cout<<(bitset<100>)(MY)<<endl; 
//	for(i=1; i<=n; ++i) dis[i]&=MY; 
//	printf("# %lld %lld %lld\n", MY, C, k); 
	k=C-(MY&C); C&=MY; 
//	printf("# %lld %lld %lld\n", MY, C, k); 
//	for(i=1; i<=n; ++i) printf("%lld ", dis[i]); printf("\n"); 
	Trie.add(0); 
	for(i=1; i<=n; ++i) {
		if(i==1) Trie.add(dis[i]); 
		if(i==n)  ans = max(ans, dis[i]^Trie.que_max(dis[i]^C)^C); 
	}
	printf("%lld", ans^k); 
	return 0;
}