@codeforces - 1205B@ Shortest Cycle

Dear 丶 2023-06-01 13:59 12阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一个长度为 n 的正整数序列 a1, a2, ..., an。

考虑建一张 n 个点的图。假如 ai AND aj ≠ 0，则在 i, j 之间连无向边。

求在这张图上的最小环。

**Input**  
第一行一个整数 n 表示序列长度 (1≤n≤10^5)  
第二行包含 n 个整数 a1,a2,…,an (0≤ai≤10^18)。

**Output**  
如果图中不含任何环，输出 -1。  
否则输出最小环长度。

**Examples**  
**Input**  
4  
3 6 28 9  
**Output**  
4

**Input**  
5  
5 12 9 16 48  
**Output**  
3

**Input**  
4  
1 2 4 8  
**Output**  
\-1

**Note**  
第一个样例答案为 (9,3,6,28)。  
第二个样例答案为 (5,12,9)。  
第三个样例没有环。

## @solution@ ##

其实是一道很 sb 的题。。。

考虑假如某个二进制位上存在至少三个数该位为 1，则存在一个长度为 3 的环，显然该环最小。  
因为最多有 60 个二进制位，每个位上存在最多 2 个数该位为 1 才有考虑的价值。  
而在这种情况，因为非 0 的元素总会占一个二进制位的 1，所以最多会有 120 个非 0 元素；而为 0 的元素就是个孤立点，不需要管它。  
所以直接当非 0 的点数 < 120（代码中写的是 300比较方便copy模板）时才用 Floyd 跑最小环，否则直接输出 3。

## @accepted code@ ##

#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int MAXN = 300; int G[MAXN + 5][MAXN + 5], A[MAXN + 5][MAXN + 5]; ll a[MAXN + 5]; int n, cnt; int main() { scanf("%d", &n); for(int i=1;i<=n;i++) { ll x; scanf("%lld", &x); if( x ) a[++cnt] = x; if( cnt > MAXN ) { puts("3"); return 0; } } for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) if( a[i] & a[j] ) A[i][j] = G[i][j] = 1; else A[i][j] = G[i][j] = MAXN + 5; int ans = MAXN + 5; for(int k=1;k<=cnt;k++) { for(int i=1;i<k;i++) for(int j=i+1;j<k;j++) ans = min(ans, A[i][k] + A[k][j] + G[i][j]); for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) G[i][j] = min(G[i][k] + G[k][j], G[i][j]); } if( ans == MAXN + 5 ) puts("-1"); else printf("%d\n", ans); }

## @details@ ##

所以，我至今不知道为什么我当时会卡在这种 sb 题上面。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11402279.html