2020-2021:teams:famerwzyyuki:线性基
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 20:32] yuki |
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 21:09] (当前版本) yuki |
||
|---|---|---|---|
| 行 329: | 行 329: | ||
| **题意：**给一个无向连通图，求一条从$1$到$n$的路径（可以不是简单路径），使经过的边权的异或和最大。\\ | **题意：**给一个无向连通图，求一条从$1$到$n$的路径（可以不是简单路径），使经过的边权的异或和最大。\\ | ||
| **题解：**首先注意到一个结论：对于所有的简单环，环上边权的异或和都可以无代价的获取。原因是可以从一号点出发进入该环绕一圈后原路返回。由于一条路径绕两边对答案的贡献为 $0$，所以这些简单环的异或和都可以无代价取得。那么现在问题就转化成了寻找一条 $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> | ||
| + | \\ | ||
2020-2021/teams/famerwzyyuki/线性基.1590755565.txt.gz · 最后更改: 2020/05/29 20:32 由 yuki
