CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2020/5/18-2020/5/24 ======
===== 团队训练 =====
[[https://www.jisuanke.com/contest/8289]]\\

===== 队伍知识点 =====
[[线性基]]\\
[[备份：线性基]]\\

===== 吕双羽 =====
=== 专题 ===
[[备份：线性基]]
=== 比赛 ===
又又又只有团队赛（但是做了线性基的题）

===== 吴湛宇 =====
我我我又只有团队赛...让我活过期末，我会回来的！

===== 陶虹宇 =====
这周又咕咕咕了，快到期末了，放过孩子吧m(，下次一定，不，两定。

===== 本周推荐 =====
===== 吕双羽 =====
==== 洛谷4151 [WC2011]最大XOR和路径 ====
**题意：**给一个无向连通图，求一条从$1$到$n$的路径（可以不是简单路径），使经过的边权的异或和最大。\\
**题解：**首先注意到一个结论：对于所有的简单环，环上边权的异或和都可以无代价的获取。原因是可以从一号点出发进入该环绕一圈后原路返回。由于一条路径绕两边对答案的贡献为 $0$，所以这些简单环的异或和都可以无代价取得。那么现在问题就转化成了寻找一条 $1$到 $n$的路径，再异或上一些简单环的异或和，最大化答案。\\
我们考虑应该寻找哪一条路径：事实上任选一条路径即可。原因是选择的路径和答案路径一定可以构成一个环，所以异或上该环的权值就可以得到最优解。
<hidden std>
<code cpp> 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
const int N=50005;
const int M=200005;
ll getin(){
    char c;bool flag=0;ll num=0ll;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=1;
    while(c>='0'&&c<='9'){num=num*10+c-48;c=getchar();}
    if(flag) num=-num;
	return num;
}
int n,m,cnt=1,fir[N],tar[M],nxt[M];
ll w[M],f[N],a[65];bool dfn[N];
inline void link(int a,int b,ll c){
	tar[++cnt]=b,w[cnt]=c;
	nxt[cnt]=fir[a],fir[a]=cnt;
}
inline void insert(ll x){
	for(int i=61;i>=0;i--)if(x&(1ll<<i)){
		if(a[i]) x^=a[i];
		else{a[i]=x;break ;}
	}
}
void dfs(int x,int last){
	dfn[x]=1;
	for(int i=fir[x];i;i=nxt[i]){
		if(i==(last^1)) continue ;
		if(!dfn[tar[i]]){
			f[tar[i]]=f[x]^w[i];
			dfs(tar[i],i);
		}
		else insert(f[x]^f[tar[i]]^w[i]);
	}
}
int main(){
	n=getin(),m=getin();
	while(m--){
		int x=getin(),y=getin();
		ll w=getin();
		link(x,y,w),link(y,x,w);
	}
	dfs(1,0);
	ll ans=f[n];
	for(int i=61;i>=0;i--)
		ans=max(ans,ans^a[i]);
	cout<<ans<<endl;
}

</code>
</hidden>
\\
CVBB ACM Team

用户工具

站点工具

页面工具
