Codeforces Round #580 (Div. 2) D Shortest Cycle（最小环）-蒲公英云

Codeforces Round #580 (Div. 2) D Shortest Cycle（最小环）

题意：给你n个数，如果每两个数且（and）不为0，可以连无向边，求最小环。

分析：最小环可以利用Floyd来搞，n太大，如果n很小就可以直接搞了，考虑把n缩小，因为最小环是3，所有只要某一位的个数大于等于3，那么肯定结果就是3，由容斥原理（鸽巢定理）可知，当非0的个数大于63*2时，肯定会有一个位的个数大于2，或者直接统计每一位的个数也行，这样就可以把n缩小到100多了，直接跑Floyd就好了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=150;
const int M=1e5+5;
ll n,cnt,ans=1e9,a[M],d[N][N],e[N][N];
int main() {
    cin>>n;
    for(int i=0; i<n; i++) {
        ll x;
        cin>>x;
        if(x) a[cnt++] = x;
    }
    if(cnt>150) {cout<<"3\n"; return 0;}
    for(int i=0; i<cnt; i++) for(int j=0; j<cnt; j++) {
        if(i!=j && a[i]&a[j]) d[i][j] = e[i][j] = 1;
        else d[i][j] = e[i][j] = 1e9;
    }
    for(int k=0; k<cnt; k++) {
        for(int i=0; i<k; i++)
            for(int j=i+1; j<k; j++)
                ans = min(ans, e[i][k] + e[k][j] + d[i][j]);
        for(int i=0; i<cnt; i++) for(int j=0; j<cnt; j++)
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }
    if(ans==1e9) cout<<"-1\n";
    else cout<<ans<<endl;
    return 0;
}