题解 CF845G 【Shortest Path Problem?】

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$ 链。

因此,这个题就解决了.

代码

#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]));
}