AtCoder Beginner Contest 408 E-F 题解

E. Minimum OR Path

题意

给你一个 \(N\) 个点 \(M\) 条边的无自环的无向图，第 \(i\) 条边连接 \(u_i\) 和 \(v_i\)，权值为 \(w_i\)。
在所有从 \(1\) 到 \(n\) 的简单路径（不经过同一点两次的路径）中，找到边权或和的最小值。
思路

贪心。把最终答案转换成二进制数看，接下来所说的高位、低位都指二进制位：
可以发现，越高位的贡献越大，而且二进制数 \(100000>011111\)，即，只要高位是 \(0\)，不管低位怎么增加都还是比原来小；
所以，要使答案最小，首先要使高位尽可能小。
那就可以从高位往低位贪心，假设一开始的答案的 \(31\) 位每一位都是 \(1\)。从第 \(31\) 位开始，假设这一位是 \(0\)，并把这个图的边全部删除（认为这个图上只有点，无边，后续逐渐加边），然后将所有的满足 \([ 其边权的(当前位)和(之前已经确定不是 1的位)不是 1]\) 的边全部加入这个图，检测这个图是否连通。
若连通，说明这一位可以为 \(0\)，且这一位为 \(0\) 时的对答案的贡献一定比为 \(1\) 时的小，所以将答案的这一位设为 \(0\)；
否则，说明这一位只能为 \(1\)，那么答案的这一位还是 \(1\)，保留原值。
接下来说一下如何判断图是否联通：使用并查集（\(\text{DSU}\)）。对于每一位，处理之前先把 \(fa_i\) 初始化为 \(i\)，然后，对于每条满足要求（上面已经说过了）的边 \((u,v)\)，将 \(fa_{find(v)}=fa_{find(u)}\)。
时间复杂度为 \(O(N+M)\times\log N)\)。
C++ 代码

[code]#include#define int long longusing namespace std;const int maxn=200005;int n,m;int fa[maxn];struct Node{        int u,v,w;}e[maxn];int find(int x){        if(fa[x]==x) return fa[x];        return fa[x]=find(fa[x]);}signed main(){        cin>>n>>m;        int one=0,zero=0;        for(int i=1;i>u>>v>>w;                e={u,v,w};        }        for(int a=30;a>=0;a--){                for(int i=1;i