D. Shortest Cycle(floyd求最小环)
Problem - D - Codeforces
给你n个整数a1,a2,..., ana1,a2,...,an。考虑n个节点的图，其中节点ii, jj (i≠ji≠j)是相连的，当且仅当，aiaiAND aj≠0aj≠0，其中AND表示位数和操作。
输入
第一行包含一个整数nn(1≤n≤105)(1≤n≤105)--数字的数量。
第二行包含n个整数a1,a2,...,ana1,a2,...,an（0≤ai≤10180≤ai≤1018）。
输出
如果该图没有任何循环，则输出-1-1。否则输出最短周期的长度。
例子
输入
拷贝
4
3 6 28 9
输出
复制
4
输入
复制
5
5 12 9 16 48
输出
复制
3
输入
复制
4
1 2 4 8
输出
复制
-1
注意
在第一个例子中，最短的周期是(9,3,6,28)(9,3,6,28)。
在第二个例子中，最短的周期是(5,12,9)(5,12,9)。
在第三个例子中，该图没有循环。
题解:
既然是求最小环,普通求最小环数据过大,所以肯定和数据有关,题中说&不为0的连边,那么如果二进制某一位上次数出现超过3,说明出现了一个为长度为3的环,环最小也就是3,
而数据只有1e18,顶多60 * 2 + 1个不为0的ai,肯定会构成一个为3的最小环
剩下的数组足够我们跑一个,floyd求最小环的板子了(由于ai可能为0,太多0也会t,所以把为0的去除,反正对答案无影响)
(记得(1 << 60) 如果像这样就会爆int,1记得加ll)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int d[204][204];
int a[100050];
int c[100];
int f[204][204];
void solve()
{int n;cin >> n;int ff = 0;for(int i = 1;i <= n;i++) {cin >> a[i];for(int j = 0;j <= 60;j++){if((1ll << j)&a[i]){c[j]++;}if(c[j] >= 3)ff = 1; }}if(ff){cout <<3<<"\\n";return ;}int len = 0;for(int i = 1;i <= n;i++){if(a[i])a[++len] = a[i];}n = len;for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){if(a[i]&a[j]){d[i][j] = 1;}else{d[i][j] = 1e8;}}}for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++)f[i][j] = d[i][j];}int ans = 1e8;for(int k = 1;k <= n;k++){for(int i = 1;i < k;i++){for(int j = i + 1;j < k;j++){if(f[i][j] + d[j][k] + d[k][i] < ans){ans = f[i][j] + d[j][k] + d[k][i];}}}for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){if(f[i][j] > f[i][k] + f[k][j]){f[i][j] = f[i][k] + f[k][j];} }}}if(ans == 1e8)cout << -1;elsecout << ans;
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;
// cin >> t;while(t--){solve(); }
}