[CF1205B] Shortest Cycle - 最小环,Floyd

有 \(n(n\leq 10^5)\) 个数 \(a_1,...,a_n\ (a\leq 10^{18})\) 。有一个图用这个方法生成，若 \(a_i\) 按位与 \(a_j\) 不为 \(0\)，则在 \(a_i,a_j\) 间连一条无向边。求这个图的最小环，若无环输出 \(-1\)。

Solution

把 \(a_i=0\) 的数字删掉

当 \(n \ge 128\) 时，至少有一个二进制位满足该位为 \(1\) 的数个数 \(\ge 3\)，即形成三元环

当 \(n<128\) 时，暴力建图后用 Floyd 跑最小环即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 205;

int n,a[N],g[N][N],f[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) {
        if(i>128) break;
        cin>>a[i];
        if(a[i]==0) --i, --n;
    }
    if(n>=128) {
        cout<<3;
        return 0;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j) f[i][j]=g[i][j]=0;
            else f[i][j]=g[i][j]=(a[i]&a[j]?1:999);
        }
    }
    int ans=999;
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) if(i!=j&&j!=k&&i!=k) {
                ans=min(ans,f[i][k]+f[k][j]+g[j][i]);
            }
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(g[i][k]+g[k][j] < g[i][j]) {
                    g[i][j]=g[i][k]+g[k][j];
                }
            }
        }
    }

    cout<<(ans>=999?-1:ans)<<endl;
}