小 ω 有一张连通无向图。她现在在点 \(1\) , 她想去点 \(n\)。
她经过多次试验，发现一条路径的权值为其中所有边权的“与”。
她现在要找一条权值最大的路径，你能帮帮她吗？
注意，图中可能存在重边自环。
\(1\leq n\leq 10^5,1\leq m\leq 5\cdot 10^5,0\leq v_i<2^{63}\)
二进制的套路，从高到低一位一位考虑 .
考虑只保留当前为为 \(1\) 的边，\(1\) 到 \(n\) 是否还联通 .
如果联通，则此位可以为 \(1\) ，把所有此为不为 \(1\) 的边删掉 .
否则，此位为 \(0\) .
时间复杂度 : \(O(63(n+m))\)
空间复杂度 : \(O(n+m)\)
code
#include<bits/stdc++.h>
using namespace std;
// long long ??!
inline long long read(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
long long res=0;
while(ch>='0'&&ch<='9'){
res=res*10ll+ch-'0';
ch=getchar();
}
return res;
}
inline void print(long long res){
if(res==0){
putchar('0');
return;
}
int a[20],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
int n,m;
bool ok[500010];
vector<pair<pair<int,int>,long long> >e;
vector<int>g[100010];
bool vis[100010];
queue<int>Q;
bool bfs(){
for(int i=0;i<n;i++)vis[i]=false;
while(!Q.empty())Q.pop();
vis[0]=true;
Q.push(0);
while(!Q.empty()){
int x=Q.front();
Q.pop();
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i];
if(!vis[to]){
vis[to]=true;
Q.push(to);
}
}
}
return vis[n-1];
}
int main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
n=read();m=read();
for(int i=0;i<m;i++){
int u=read()-1,v=read()-1;
long long w=read();
e.push_back(make_pair(make_pair(u,v),w));
ok[i]=true;
}
long long ans=0;
for(int k=62;k>=0;k--){
for(int i=0;i<n;i++)g[i].clear();
for(int i=0;i<m;i++)if(ok[i]){
if(e[i].second&(1ll<<k)){
g[e[i].first.first].push_back(e[i].first.second);
g[e[i].first.second].push_back(e[i].first.first);
}
}
if(bfs()){
ans+=1ll<<k;
for(int i=0;i<m;i++)if(!(e[i].second&(1ll<<k)))ok[i]=false;
}
}
print(ans);
putchar('\n');
return 0;
}
/*inline? ll or int? size? min max?*/