Codeforces Round #580 Shortest Cycle（Floyd求最小环）

Shortest Cycle

题意：给定 $1e5$1e5个点的 $a\left[i\right]$a[i]，任意两个点 $i,j$i,j之间存在无向边当且仅当 $a\left[i\right]$a[i] & $a\left[j\right]!=0$a[j]!=0，求周长最小的环

思路：

1. 将所有的 $a\left[i\right]$a[i]看作二进制形式，则若两个点之间没有边，说明二者的二进制位没有公共的 $1$1；
2. 同时，若所有的点没有形成环，说明在 $63$63个二进制位上没有哪一位有三个点（否则这三个点直接形成最小的环，周长为 $3$3）；
3. 而这种情况显然最多只能有 $126$126个点共存
4. 因此当点数大于 $126$126时，可以直接输出 $3$3，否则用Floyd以 $O\left(n^3\right)$O(n3)的复杂度跑出最小环
5. Floyd跑最小环考虑建立两个数组： $g\left[i\right]\left[j\right]$g[i][j]和 $d\left[i\right]\left[j\right]$d[i][j]，其中 $g\left[i\right]\left[j\right]$g[i][j]表示 $i,j$i,j两点是否存在直接的连边， $d\left[i\right]\left[j\right]$d[i][j]表示 $i,j$i,j的最短距离
6. 在Floyd循环的最内层用点 $k$k更新点 $i,j$i,j最短距离之前，先考虑 $i,j,k$i,j,k是否可以成环，若能成环，则更新答案
7. 能否成环的判定条件： $g\left[i\right]\left[k\right]$g[i][k]&& $g\left[k\right]\left[j\right]$g[k][j]&& $d\left[i\right]\left[j\right]\&lt;inf$d[i][j]<inf
8. 最后需要注意： $a\left[i\right]$a[i]可能为 $0$0，且为 $0$0的点不与任何点存在连边，因此是无效点，需要删去

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, ans;
ll a[maxn];
int g[130][130], d[130][130];

int Floyd() {
    for(int i=1; i<n; ++i)
        for(int j=i+1; j<=n; ++j)
            if(a[i]&a[j]) g[i][j]=g[j][i]=1, d[i][j]=d[j][i]=1;
            else g[i][j]=g[j][i]=0, d[i][j]=d[j][i]=130;
    ans=130;
    for(int k=1; k<=n; ++k) {
        for(int i=1; i<=n; ++i) {
            if(i==k) continue;
            for(int j=1; j<=n; ++j) {
                if(i==j||k==j) continue;
                if(g[i][k]&&g[k][j]&&d[i][j]<130) ans=min(ans,d[i][j]+2);
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    if(ans>n) return printf("-1\n"), 0;
    return printf("%d\n", ans), 0;
}

int main() {
    //ios::sync_with_stdio(false);
    n=read();
    for(int i=1; i<=n; ++i) {
        scanf("%lld", &a[i]);
        if(!a[i]) --i, --n;
    }
    if(n<130) return Floyd();
    puts("3");
}