题解 CF845G 【Shortest Path Problem?】
顾z
2018-11-05 20:29:49
> ### Description
>
> 给定一张 $n$ 个点 $m$ 条边的无向图，一开始你在点 $1$，且价值为 $0$
>
> 每次你可以选择一个相邻的点，然后走过去，并将价值异或上该边权
>
> 如果在点 $n$，你可以选择结束游戏
>
> 求一种方案，使得结束游戏后价值最小
>
> $n,m \le 10^5$
>
> ### Input
>
> 第一行为两个整数$n,m$代表有$n$个点$m$条边。
>
> 接下来$m$行,描述一条从$x$到$y$长度为$z$的无向边。
>
> ### Output
>
> 一个整数,代表最小价值。
首先,很明确的一点,题目要求我们求出很多条边的最小异或和。
由此,我们可以想到**线性基**
由于我们可以重复经过一些边,那么根据异或性质,当这条边被重复走过两次,那它对答案的贡献就是$0$。但是即使这样,它还可能连向其他的点。
虽然我们没办法枚举边,但是可以考虑将这些边所在分为两种。
1. 环上的边
2. 链上的边
但是我们**通向一个环的时候会经过一条连向这个环的边两次**。(一进一出)。
因此,我们考虑**维护每个环的异或和,塞入线性基中**。
再找一条链,去和其异或起来最小。即可。
**这条链可以随便选择**。
简单证明一下;
> 假设存在两条链$A,B$，我们现在选择了不优的$A$链,但是在求解答案的时候(利用线性基)
>
> 我们会异或到一个环($A,B$链围成的环),这时,就好比我们原路返回,又选择了较优的$B$链。
因此,这个题就解决了.
``代码``
```c++
#include<cstdio>
#include<algorithm>
#include<iostream>
#define R register
#define lo long long
using namespace std;
const int gz=1e5+8;
inline void in(R int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int head[gz<<1],tot;
struct cod{int u,v;lo w;}edge[gz<<2];
lo p[64],dis[gz];
inline void add(R int x,R int y,R lo z)
{
edge[++tot].u=head[x];
edge[tot].v=y;
edge[tot].w=z;
head[x]=tot;
}
int n,m;
bool vis[gz];
inline void ins(R lo x)
{
for(R int i=63;i>=0;i--)
{
if((x>>i)&1LL)
{
if(p[i])
x^=p[i];
else
{
p[i]=x;
break;
}
}
}
}
inline lo query(R lo o)
{
R lo res=o;
for(R int i=63;i>=0;i--)
if((res^p[i])<res)res^=p[i];
return res;
}
void dfs(R int u,R lo now)
{
vis[u]=true;dis[u]=now;
for(R int i=head[u];i;i=edge[i].u)
{
if(!vis[edge[i].v])
dfs(edge[i].v,now^edge[i].w);
else ins(now^edge[i].w^dis[edge[i].v]);
}
}
int main()
{
in(n);in(m);
for(R int i=1,x,y;i<=m;i++)
{
R lo z;
in(x),in(y);
scanf("%lld",&z);
add(x,y,z),add(y,x,z);
}
dfs(1,0);
printf("%lld\n",query(dis[n]));
}
```