codeforces-1205B-Shortest Cycle题解

发表于 更新于 分类于 阅读次数：

描述

给一个数组nums, 对于里面的任意两个数字a和b, 如果a & b != 0, 说明a和b是连通的. (每个数字可以看做一个节点) 求这些数字组成的图中, 最小环的长度. 如果没有环, 返回-1.
数组长度最大100000.

思路

如果所有节点两两判断是否连通, 复杂度肯定吃不消. 考虑所有数字(都是64位), 每一位可以看做是用来和其他数字连通的接口,

  • 比如第一位(最低位), 如果所有数字中, 有>=3个数字在这一位是1, 那么最小环的长度一定是3.
  • 如果对于某一位, 所有数字中, 这一位全是0, 那么相当于这个接口没有被用到. 两个数字a和b就算连通, 也不是因为这一位的贡献.
  • 如果对于某一位, 所有数字中, 只有一个数字在这一位是1, 其他全是0, 那么也相当于这个接口没有被用到(没有和它匹配的数字).
  • 所以, 真正有价值的信息是出现了正好2次的位中. 64位中, 就算出现2次bit1的位置完全分散开, 也只有64*2=128个数字. 对于这最多128个数字, 可以用floyd算法找最小环. 复杂度O(n**3)可以接受.

关于WA了一次的floyd

为什么要写成下面这样, 而不能更新完多源最短路径, 再求最小环呢? 

1
2
3
4
5
6
7
8
9
for k in range(nv): # k是中间点, 相当于[i]-----[k]-----[j]~[i](成环)
    for i in range(k):
        for j in range(k):
            if i != j:
                res = min(res, dis[i][j] + mp[j][k] + mp[k][i])
    for i in range(nv):
        if k != i:
            for j in range(nv):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])

最内层每一次更新res和dis[i][j]都是针对上一层k-1的值来说的. 也就是对于环内节点最大是k的环来说, i和j的距离, 以及最小环长度. 如果完全更新完dis矩阵, 那么dis[i][j]这条最短路可能包含了当前的k, 再和dis[i][k], dis[k][j]相加没有意义.

上面其实也是floyd算法求(无向图)最小环的模板代码. (k为什么写在最外面?: https://www.zhihu.com/question/30955032)

代码

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
def do():
    n = int(input())
    nums = [int(c) for c in input().split(" ")]
    valid = set()
    for i in range(64):
        count = []
        for j in range(n):
            if (1 << i) & nums[j]:
                count.append(nums[j])
            if len(count) == 3:
                return 3
        if len(count) == 2:
            valid.add(count[0])
            valid.add(count[1])
    # valid won't be that large hahaha at most 64*2
    nv = len(valid)
    valid = list(valid)
    dis = [[float('inf')] * nv for _ in range(nv)]
    for i in range(nv):
        for j in range(nv):
            if i == j:
                dis[i][j] = 0
            elif valid[i] & valid[j]:
                dis[i][j] = 1
    mp = [[_ for _ in dis[i]] for i in range(len(dis))] # 原始的邻接矩阵
    res = nv + 1
    for k in range(nv):   
        for i in range(k):
            for j in range(k):
                if i != j:
                    res = min(res, dis[i][j] + mp[j][k] + mp[k][i])
        for i in range(nv):
            if k != i:
                for j in range(nv):
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return res if res <= nv else -1
 
print(do())