前情提要

本题与这一道或最小生成树思路一样，做完本题可以做这一道巩固一下。

题目大意

给你一个连通无向图，求 $1$ 到 $n$ 的简单路径的边权之或的最小值。

思路分析

看到路径的最小值，首先想起最短路，用 dijkstra？但立即意识到不太行，并不是一个边权越大它与另个一个值按位或的值就会越大。

接下来以按位或的性质作为突破口。位运算中不同位是相对独立的，我们可以考虑从每一位枚举。

如果答案的第 $i$ 位可以为 $0$，无论后面其它位是多少和都不会超过 $2^{i-1}$。 即若能取 $0$ 则永远比取 $1$ 优。所以我们从高位到低位贪心，尽量让高位不要取 $1$，如果可以取 $0$ 就取 $0$。

注意到数据范围 $0\leq w <2^{30}$，枚举 $0\leq i \leq 30$。什么时候这一位必须要取 $1$ 呢？当只用这一位是 $0$，且前几位满足之前枚举的要求的边无法使 $1$ 与 $n$ 连通时，这一位就只能取 $1$ 了。

举个例子 第一个样例：

  • 当 $i=2$ 时，我们去掉所有第 $3$ 位是 $1$ 的边，发现 $1$->$2$->$3$->$4$ 仍然可以到达，那我们就不取，$ans=(000)_2$。

  • 当 $i=1$ 时，我们不仅不能取第 $2$ 位是 $1$的边，还要满足之前的条件，即第 $3$ 位是 $1$ 的不取。发现 $1$ 到不了 $4$ 了，于是这一位必须是 $1$，$ans=(010)_2$。

  • 当 $i=0$ 时,和之前一样，但由于 $ans$ 第 $2$ 位已经取 $1$，我们可以取第 $2$ 位是 $1$的边。发现不连通，$ans=(011)_2=3$。

代码细节

判断图联通可以用 bfs 等一系列方法，这里我采用并查集，并使用 $vis$ 数组判断该边可不可以使用。时间复杂度 $O((m+n)·\log(m))$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,fa[N],ans,num[N];
struct node{
    int u,v,w;
}e[N];
bool vis[N];
int find(int x){return (x==fa[x])?x:(fa[x]=find(fa[x]));}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) fa[x]=y;
}
signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[i]={u,v,w};
    }
    for(int i=1;i<=max(n,m);i++) fa[i]=i,vis[i]=0;
    for(int i=30;i>=0;i--){
        int cnt=n;
        for(int j=1;j<=m;j++){
            if(vis[j]) continue;
            if(!(e[j].w&(1<<i))) merge(e[j].u,e[j].v);//这一位可以取	
        }
        if(find(1)==find(n)){
            for(int j=1;j<=m;j++){
                if(e[j].w&(1<<i)) vis[j]=1;
            }	
        }
        else ans+=(1<<i);
        for(int j=1;j<=n;j++) fa[j]=j;
    } 
    printf("%d\n",ans);
    return 0;
}