题目地址

https://codeforces.com/contest/1206/problem/D

题目大意

给n个数字(n是1e5级),如果a[i]&a[j]!=0，则i点到j点有连边，问最短的环长度是多少。

解法

先按位扫数组，如果一个位在数字上出现的次数超过了三次，那么这三个数字可以直接成环，输出答案3.

接下来讨论每个位最多两个数字的情况，这种情况最多只有2*64个数字，因此算法的复杂度可以比较大。但要记得筛除a[i]=0的情况。

那么floyd是怎么求最小环的呢？

rep(i,1,n)
    rep(j,1,n)
        mp[i][j]=e[i][j];//把一开始的e复制一遍给mp
rep(k,1,n){
    //当循环到k的时候,可以保证之前的e[i][j]路径中都不会包含k
    rep(i,1,k-1){
        rep(j,i+1,k-1){
            minn = min(minn,e[i][j]+mp[i][k]+mp[j][k]);//i->j->k->i这个环长度
            //这句后面两个一定要是mp！一开始错在这里
            //想明白了是因为圈上会有边被经过两次,类似丫字型,原本不能成环,但如果不是mp会被误判成环
        }
    }
    rep(i,1,n){
        rep(j,1,n){
            e[i][j]=min(e[i][j],e[i][k]+e[k][j]);//这样处理之后,路径可以包含k
        }
    }
}

可以比较直观地看到，第一层枚举k，内层的i和j都不会大于k，这样就保证了新加入的点k不在任何的eij路径中。那么这样一来，i->j是i到j的一条路径,i->k->j是第二条路径，这样一来就是一个环。在这些解里面找最小值即可。

！之前比较疑惑的点就是，为什么要保留最初的邻接矩阵e在mp中呢？

因为如果都使用数组e，即minn = min(minn,e[i][j]+mp[i][k]+mp[j][k])，在这种情况下会出错：

tu1

显然原本是不能成环的，但是$e_{i,k}$和$e_{j,k}$都有值，这样在minn = min(minn,e[i][j]+mp[i][k]+mp[j][k])下是有解的，实际上这条路径用了重复的路，所以没环，就出错了。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
#define INF 0x3f3f3f3f

const int MAXN = 114514;
ll a[MAXN];
int e[666][666],mp[666][666];
int n;
vector<ll> vec;
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    ll tmp;
    rep(i,0,63){
        tmp = 1ll<<i;
        int cnt = 0;
        rep(i,1,n)
            if(a[i]&tmp) cnt++;
        if(cnt>=3){
            cout<<3<<endl;
            return;
        }
    }
    vec.push_back(-1);//填个空
    rep(i,1,n)
        if(a[i]!=0) vec.push_back(a[i]);//防止0的情况
    n = vec.size()-1;
    //最多2*64个数，floyd找最小环
    int minn = INF;
    rep(i,1,n){
        rep(j,1,n){
            e[i][j] = INF/3;//INF的话会越界
            if(i==j) e[i][j]=0;
            else if(vec[i]&vec[j]) e[i][j]=1;
        }
    }
    //floyd
    rep(i,1,n)
        rep(j,1,n)
            mp[i][j]=e[i][j];//把一开始的e复制一遍给mp
    rep(k,1,n){
        //当循环到k的时候,可以保证之前的e[i][j]路径中都不会包含k
        rep(i,1,k-1){
            rep(j,i+1,k-1){
                minn = min(minn,e[i][j]+mp[i][k]+mp[j][k]);//i->j->k->i这个环长度
                //这句后面两个一定要是mp！一开始错在这里
                //想明白了是因为圈上会有边被经过两次,类似丫字型,原本不能成环,但如果不是mp会被误判成环
            }
        }
        rep(i,1,n){
            rep(j,1,n){
                e[i][j]=min(e[i][j],e[i][k]+e[k][j]);//这样处理之后,路径可以包含k
            }
        }
    }
    if(minn>n) cout<<-1<<endl;
    else cout<<minn<<endl;
}

int main(){
    solve();
}