AT_abc408_e 题解

· · 题解

还是很兴奋的。

最近打 ABC 状态不咋好，这回搞了 5 题，还是很兴奋的。

行吧！那就来讲讲这个题目吧！

就是给你一个图，有 n 个点，m 条无向边，每条边呢还有一个权值。要你找到从 1 到 n 的所有简单路径中，经过的边的权值或值最小的。要求输出这个或值。

首先可以打一个暴搜。肯定是对的，是吧，但是会超时。我赛时就是这样傻乎乎弄了一次，然后吃了一发罚时。

考虑到是或运算，肯定是有问题的。普通的搜索肯定过不了。

涉及到位运算，一般都是拆位，是吧？那就往这个方向想。

我们从高位开始枚举。为什么不从低位开始？因为有一条显而易见的结论：如果当前这一位可以为 0，肯定是比当前这一位为 1 的答案优的。为啥啊，因为后面的所有都为 1 也超不过现在这一位为 1。

那就行了。从高位开始枚举，尝试让最终答案的这一位填上 0。那咋整？并查集！

我们枚举每一条边，如果这个边的权值 w 在当前枚举到的这一位上确实是 0，我们就可以用并查集把这个边连接的两个点弄到一个集合里去。

枚举完了，我们就判断一下，1 和 n 是不是联通的。如果是，那么这一位就可以为 0；不是的话，这一位就只能是 1 咯，那 ans 就要加上这一位为 1 的答案了。

最后输出就可以了。

编起来很简单的，但还是附一份赛时代码吧。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
struct line{int u,v,w;}ln[N];
int n,m,ans,fa[N];bool is[N];
int FF(int u){return (fa[u]==u?u:fa[u]=FF(fa[u]));}
void Merge(int u,int v){fa[FF(v)]=FF(u);return;}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>ln[i].u>>ln[i].v>>ln[i].w;
    for(int x=29;x>=0;x--){
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=1;i<=m;i++){
            if((ln[i].w>>x)&1)continue;bool OK=1;
            for(int o=29;o>x;o--)if(!is[o]&&((ln[i].w>>o)&1))OK=0;
            if(!OK)continue;
            if(FF(ln[i].u)!=FF(ln[i].v))Merge(ln[i].u,ln[i].v);
        }
        if(FF(1)!=FF(n))is[x]=1,ans|=(1<<x);
    }
    cout<<ans<<"\n";
    return 0;
}

如果觉得本篇题解还不错的话，麻烦你点一个小小的赞，万分感谢！