BZOJ2115 [Wc2011] Xor

题面

样例输入

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

样例输出

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

思路

真是一道代码极短思维难度高的题目。我们考虑异或的性质,这题边可以走多次,那么我们考虑把图中的每个环的异或和都加入线性基。并将随便一条1到N的简单路径的异或和加入,具体情况看图。

如图中,我们选取绿色的路径,那么绿色路径的异或和与左边的环异或和异或就可以得到红色路径,红色路径与右边的环异或和异或即可得到黄色路径,如果将绿色路径与右边的环异或和异或则可得到蓝色路径,这就是全部的路径情况,最长的路径异或和用线性基维护即可。

代码

#include<bits/stdc++.h>
#define Maxn 50005
#define Maxm 100005
#define LL long long
LL N,M,head[Maxn],dis[Maxn],cnt=0,p[65];
bool vis[Maxn];
struct edge{LL next,to,dis;}e[Maxm<<1];
using namespace std;
inline void read(LL &x)
{
	LL f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void add(LL x,LL y,LL z){e[++cnt].next=head[x];e[cnt].to=y;e[cnt].dis=z;head[x]=cnt;}
inline void insert(LL x)
{
	for (LL i=62;i>=0;i--)
	{
		if (!(x>>i&1)) continue;
		if (!p[i]) {p[i]=x;return;}
		x^=p[i];
	}	
} 
inline void dfs1(LL now,LL fa)
{
	vis[now]=1;
	for (LL i=head[now];i;i=e[i].next)
	{
		LL v=e[i].to;
		if (v==fa) continue;
		if (!vis[v]) {dis[v]=dis[now]^e[i].dis;dfs1(v,now);}
		else insert(dis[now]^dis[v]^e[i].dis);
	}
}
int main()
{
	read(N),read(M);
	for (LL i=1;i<=M;i++) 
	{
		LL s,t,d;
		read(s),read(t),read(d);
		add(s,t,d),add(t,s,d);
	}
	dfs1(1,1);
	LL ans=dis[N];
	for (LL i=62;i>=0;i--) if ((ans^p[i])>ans) ans^=p[i];
	cout<<ans<<endl;
	return 0;
} 
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇