sol

首先很显然的，答案等于1到n的任意一条路径的异或和与若干个环的异或和的异或和。

因为图是联通的，那么就可以从一个点走到任意一个想要走到的环上，走完这个环后原路返回，那么中间的路径刚好抵消，所以这样是成立的。

现在需要把所有环的异或和丢到一个线性基里面。在dfs的生成树上的每一条非树边（返祖边）都对应了一个环，直接丢进去就可以了。

code

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

ll gi()

{

	ll x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

struct xxj{

	ll p[70];

	void insert(ll x)

		{

			for (int j=63;j>=0;--j)

			{

				if (!(x>>j)) continue;

				if (!p[j]) {p[j]=x;return;}

				x^=p[j];

			}

		}

	ll query(ll x)

		{

			for (int j=63;j>=0;--j)

				x=max(x,x^p[j]);

			return x;

		}

}S;

const int N = 1e5+5;

int n,m,to[N<<1],nxt[N<<1],head[N],cnt,vis[N];ll val[N<<1],dis[N];

void link(int u,int v,ll w){to[++cnt]=v;nxt[cnt]=head[u];val[cnt]=w;head[u]=cnt;}

void dfs(int u)

{

	for (int e=head[u];e;e=nxt[e])

		if (!vis[to[e]])

			dis[to[e]]=dis[u]^val[e],vis[to[e]]=1,dfs(to[e]);

		else S.insert(dis[to[e]]^dis[u]^val[e]);

}

int main()

{

	n=gi();m=gi();

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

	{

		int u=gi(),v=gi();ll w=gi();

		link(u,v,w);link(v,u,w);

	}

	dfs(1);printf("%lld\n",S.query(dis[n]));

	return 0;

}

巴特西

[BZOJ2115][WC2011]最大XOR和路径

sol

code

最新文章

热门文章