题目链接：Codeforces 1026D
根据鸽巢原理，当抽屉数量为 \(64\) 的时候，如果大于 \(64 \times 2 + 1 = 129\) 个物品，可以保证有一个抽屉中出现三个物品。也就是说，在这一题中，我们只需要去掉所有为零的元素，在剩下的 \(r\) 个元素中随意取 \(\min \{ r, 129 \}\) 个出来寻找最小环即可。
这里可以使用 Floyd 算法求最小环，时间复杂度 \(O(129 ^ 3)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
const int MAX_V = 129 + 5;
const LL INF = LL(1E15);
int n, tot, up;
LL a[MAX_N], b[MAX_N];
LL v[MAX_V][MAX_V], d[MAX_V][MAX_V];
LL minCir = INF;
void floyd() {
for (int i = 1; i <= up; ++i) {
for (int j = 1; j <= up; ++j) {
d[i][j] = v[i][j];
}
}
for (int k = 1; k <= up; ++k) {
for (int i = 1; i < k; ++i) {
for (int j = 1; j < i; ++j) {
minCir = min(minCir, d[i][j] + v[i][k] + v[k][j]);
}
}
for (int i = 1; i <= up; ++i) {
for (int j = 1; j <= up; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
for (int i = 1; i <= n; ++i) if (a[i]) b[++tot] = a[i];
up = min(tot, 129);
for (int i = 1; i <= up; ++i) {
for (int j = i + 1; j <= up; ++j) {
if (b[i] & b[j]) {
v[i][j] = v[j][i] = 1;
} else {
v[i][j] = v[j][i] = INF;
}
}
}
floyd();
if (minCir == INF) puts("-1");
else printf("%lld\n", minCir);
return 0;
}
|