CF1659E AND-MEX Walk 题解

· · 题解

可能更好的阅读体验
题目传送门

题目大意

给定一个无向带权图，总共有 n 个点 m 条边，选定一个起点 u 和终点 v，现在你需要确定一条路径，设路径上的 k 条边的边权为 w_1,w_2,\dots,w_k，求出 \operatorname{MEX}\left(\{w_1,w_1 \& w_2,w_1\&w_2\&w_3,\dots,w_1\&w_2\&\dots\&w_k\}\right) 的最小值。其中 MEX 指集合中最小的不存在的自然数。
数据范围：n,m\le 10^5，边权 \le 2^{30}。

题目解析

设路径上的 k 条边的边权为 w_1,w_2,\dots,w_k，为了方便设序列 w_1,w_1 \& w_2,w_1\&w_2\&w_3,\dots,w_1\&w_2\&\dots\&w_k 的第 i 项为 a_i。

首先我们通过样例发现一个结论：答案只可能是 0,1,2。
其实就是证明答案不是 0,1 的时候答案为 2,证明如下：
我们发现序列 \{a_n\} 不增。
如果答案不是 0,1，那么序列中就一定存在 0,1，如果答案不是 2，那么肯定存在一个数字 i 使得 a_i=2 并且 a_{i+1}=1，也就是说 2\&w_{i+1}=1，显然不成立。

这样我们只需要判断答案是否为 0，然后判断答案是否为 1，如果都不是那么答案就是 2。

答案为 0 的时候很简单，我们只需要判断是否从 u 到 v 存在一条路径，使得这条路径上的所有边权在二进制下某一位都为 1。只需要每一位建立一个并查集就可以了。

然后就是答案为 1 的情况了。
不难发现答案为 1 的时候，一定存在一个 r 使得 \forall i\le r,a_i>1 并且 a_{r+1}=0。
换句话说，只要在走这一条边之前的与和大于 1，走之后与和为 0 就可以了，然后接下来怎么走都可以，所以这样答案与终点无关。
那么怎么得到这样一条路径呢？
显然我们需要选定一位 i（不能是二进制下最低的一位！），然后从出发点走遍所有边权二进制这一位为 1 的边，然后我们只需要找是否存在一条边能够让与和变成 0。
具体用代码实现的话需要利用前面建立的并查集，并且记录每一个点所有的出边的边权的与和 f_i，然后算出在同一个联通块里面的点 f_i 的与和，如果是 0 代表这一个联通块内的点作为出发点可以做到答案为 1。

如果答案不是 0 也不是 1，那么答案就是 2 了。

代码：

#include<cstdio>
#define gc getchar
#define maxn 100039
using namespace std;
int read(){
    char c=gc(); int s=0; int flag=0;
    while((c<'0'||c>'9')&&c!='-') c=gc(); if(c=='-') c=gc(),flag=1;
    while('0'<=c&&c<='9'){ s=(s<<1)+(s<<3)+(c^48); c=gc(); }
    if(flag) return -s; return s;
}
int n,m,u,v,w,T,fa[30][maxn],f[maxn],s[maxn],flag[maxn];
int getfa(int x,int y){ if(fa[x][y]==y) return y; else return fa[x][y]=getfa(x,fa[x][y]); }
int check0(){ int i; for(i=0;i<30;i++) if(getfa(i,u)==getfa(i,v)) return 1; return 0; }
int main(){
    n=read(); m=read(); int i,j,k; for(i=0;i<30;i++) for(j=1;j<=n;j++) fa[i][j]=j;
    for(i=1;i<=n;i++) f[i]=(1<<30)-1;
    for(i=1;i<=m;i++){
        u=read(); v=read(); w=read(); f[u]&=w; f[v]&=w;
        for(j=0;j<30;j++) if(w&(1<<j)) fa[j][getfa(j,u)]=getfa(j,v);
    }
    for(k=1;k<30;k++){
        for(i=1;i<=n;i++) s[i]=(1<<30)-1;
        for(i=1;i<=n;i++) s[getfa(k,i)]&=f[i];
        for(i=1;i<=n;i++) if(s[getfa(k,i)]==0) flag[i]=1;
    } T=read(); while(T--){
        u=read(); v=read(); if(check0()) puts("0"); else if(flag[u]) puts("1"); else puts("2");
    } return 0;
}