P4151（线性基）最大异或和路径+视频讲解

细节在视频中：

P4151洛谷最大异或和路径

参考代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int maxn = 1e6 + 5;
ll bas[65];
void ins(ll x)
{
	for (ll i = 60; ~i; i--)
	{
		if ((x >> i) & 1)
		{
			if (!bas[i])
			{
				bas[i] = x;
				break;
			}
			else
				x ^= bas[i];
		}
	}
}
struct node
{
	ll v, w, nex;
} edge[maxn << 1];
ll head[maxn], cnt, dis[maxn], vis[maxn];
void add(ll u, ll v, ll w)
{
	edge[cnt].v = v, edge[cnt].w = w, edge[cnt].nex = head[u];
	head[u] = cnt++;
}
void dfs(ll u)
{
	vis[u] = 1;
	for (ll i = head[u]; ~i; i = edge[i].nex)
	{
		ll v = edge[i].v, w = edge[i].w;
		if (!vis[v])
		{
			dis[v] = dis[u] ^ w;
			dfs(v);
		}
		else
		{
			ins(dis[v] ^ dis[u] ^ w);
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n, m;
	cin >> n >> m;
	memset(head, -1, sizeof head);
	for (ll i = 0; i < m; i++)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		add(u, v, w), add(v, u, w);
	}
	dfs(1);
	ll ans = dis[n];
	for (ll i = 60; ~i; i--)
	{
		if ((ans ^ bas[i]) > ans)
			ans ^= bas[i];
	}
	cout << ans << endl;
}

本文地址：https://blog.csdn.net/yangzijiangac/article/details/107385354