题解 | #星际虫洞网络#

星际虫洞网络

https://www.nowcoder.com/practice/33e906ddf2464a9fa7dc8e9084a66f49

REALHW80 星际虫洞网络

题目链接

星际虫洞网络

题目描述

在遥远的未来，人类已步入深空探索时代。一份星图包含了 $N$ 个未知星系，每个星系 $i$ 都被赋予了一个独特的空间量子签名 $s_i$ 。

两个星系 $i$ 和 $j$ 之间能建立虫洞（边），当且仅当它们的空间量子签名发生“谐波共振”，即两个签名的按位与 (Bitwise AND) 运算结果不为零： $s_i \ \& \ s_j \neq 0$ 。

您的任务是分析给定的星系网络，找出其中最短的航行回路（即图论中的“环”）。一个有效的回路必须至少包含 3 个星系。回路的长度定义为它所包含的虫洞数量。如果网络中不存在任何回路，则报告该情况。

输入描述:

第一行是一个整数 $N$ ( $3 \le N \le 2000$ )，代表星系总数。第二行是 $N$ 个用空格分隔的整数 $s_i$ ( $0 \le s_i \le 10^{18}$ )，代表每个星系的空间量子签名。签名值可能为 0 或出现重复。

输出描述:

输出一个整数，表示最短航行回路的长度。如果不存在任何回路，则输出 -1。

解题思路

本题要求解一个特殊规则构成的无权图中的最短环问题。暴力建图然后对每条边进行 BFS 寻环的复杂度过高。我们需要利用 按位与不为零 这一连接规则的特性来优化算法。

1. 核心思想：图变换

问题的关键在于，两个星系有连接，等价于它们的二进制表示中至少有一个相同的 1 的位置。这启发我们将原问题图进行变换，构建一个星系-比特位的二分图模型：

图的一侧是星系节点（ $N$ 个）。
图的另一侧是比特位节点（最多 64 个，因为签名是 long long 类型）。
当星系 $i$ 的签名的第 $k$ 位为 1 时，我们就在星系节点 $g_i$ 和比特位节点 $b_k$ 之间连一条边。

2. 路径与环的映射关系

在这个新图中：

原图中的一条边 $(g_i, g_j)$ ，对应新图中的一条长度为 2 的路径 $g_i \leftrightarrow b_k \leftrightarrow g_j$ （其中 $k$ 是它们共享的某个比特位）。
原图中的一个长度为 $L$ 的环，会对应新图中的一个长度为 $2L$ 的环。

因此，我们的目标被转化为：寻找这个新图中的最短环，然后将其长度除以 2。

3. 高效寻环算法

新图的节点数约为 $N+64$ ，我们可以高效地在其中寻找最短环。

BFS 寻环：从图上任意一点 u 出发进行广度优先搜索 (BFS)，当遇到一个已经访问过的节点 v (且 v 不是 u 在BFS树中的父节点) 时，就找到了一个环。环的长度为 dist(u) + dist(v) + 1。
优化起点：为了确保找到全局最短环，理论上需要从每个节点都进行一次搜索。但我们可以只从数量较少的一侧，即比特位节点（最多64个）出发进行 BFS，即可覆盖所有可能的环，大大降低了计算量。

4. 算法步骤

预处理：
- 读取输入，将所有非零且不重复的签名存入一个新列表。如果有效签名数量小于3，则不可能有环，直接返回 -1。
3-环捷径：
- 这是一个非常有效的优化。如果存在某一个比特位，在 3 个或更多的星系签名中都为 1，那么这 3 个星系在原图中必然两两相连，构成一个长度为 3 的环。这是最短可能的环，可以直接返回 3。
构建星系-比特位图：
- 根据有效签名列表，构建上述二分图的邻接表。
从比特位节点 BFS：
- 初始化最小环长度 min_len 为无穷大。
- 遍历所有存在连接的比特位节点，以其为起点执行 BFS。
- 在 BFS 过程中，记录每个节点到起点的距离 dist 和其父节点 parent。
- 当从节点 u 探索到邻居 v 时，若 v 已被访问过且不是 u 的父节点，则发现一个环。环长为 dist[u] + dist[v] + 1。用 (环长 / 2) 更新 min_len。
返回结果：
- 如果 min_len 仍为无穷大，则没有环，返回 -1；否则返回 min_len。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    set<long long> s;
    for (int i = 0; i < n; ++i) {
        long long sign;
        cin >> sign;
        if (sign != 0) {
            s.insert(sign);
        }
    }

    vector<long long> signs(s.begin(), s.end());
    int m = signs.size();

    if (m < 3) {
        cout << -1 << endl;
        return 0;
    }

    for (int i = 0; i < 63; ++i) {
        int count = 0;
        for (long long sign : signs) {
            if ((sign >> i) & 1) {
                count++;
            }
        }
        if (count >= 3) {
            cout << 3 << endl;
            return 0;
        }
    }

    vector<vector<int>> adj(m + 63);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 63; ++j) {
            if ((signs[i] >> j) & 1) {
                adj[i].push_back(m + j);
                adj[m + j].push_back(i);
            }
        }
    }

    int min_len = INF;

    for (int i = 0; i < 63; ++i) {
        int start_node = m + i;
        if (adj[start_node].empty()) continue;

        queue<int> q;
        vector<int> dist(m + 63, -1);
        vector<int> parent(m + 63, -1);
        
        q.push(start_node);
        dist[start_node] = 0;
        
        int head = 0;
        vector<int> q_vec;
        q_vec.push_back(start_node);

        while(head < q_vec.size()){
            int u = q_vec[head++];

            for(int v : adj[u]){
                if(v == parent[u]) continue;
                if(dist[v] == -1){
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q_vec.push_back(v);
                } else {
                    min_len = min(min_len, dist[u] + dist[v] + 1);
                }
            }
        }
    }

    if (min_len == INF) {
        cout << -1 << endl;
    } else {
        cout << min_len / 2 << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Long> s = new HashSet<>();
        for (int i = 0; i < n; i++) {
            long sign = sc.nextLong();
            if (sign != 0) {
                s.add(sign);
            }
        }

        List<Long> signs = new ArrayList<>(s);
        int m = signs.size();

        if (m < 3) {
            System.out.println(-1);
            return;
        }

        for (int i = 0; i < 63; i++) {
            int count = 0;
            for (long sign : signs) {
                if (((sign >> i) & 1) == 1) {
                    count++;
                }
            }
            if (count >= 3) {
                System.out.println(3);
                return;
            }
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < m + 63; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < 63; j++) {
                if (((signs.get(i) >> j) & 1) == 1) {
                    adj.get(i).add(m + j);
                    adj.get(m + j).add(i);
                }
            }
        }

        int minLen = Integer.MAX_VALUE;

        for (int i = 0; i < 63; i++) {
            int startNode = m + i;
            if (adj.get(startNode).isEmpty()) continue;

            Queue<Integer> q = new LinkedList<>();
            int[] dist = new int[m + 63];
            int[] parent = new int[m + 63];
            Arrays.fill(dist, -1);
            Arrays.fill(parent, -1);

            q.offer(startNode);
            dist[startNode] = 0;

            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (v == parent[u]) continue;
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        parent[v] = u;
                        q.offer(v);
                    } else {
                        minLen = Math.min(minLen, dist[u] + dist[v] + 1);
                    }
                }
            }
        }

        if (minLen == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(minLen / 2);
        }
    }
}

import sys
from collections import deque

def solve():
    n = int(input())
    signs_full = list(map(int, input().split()))
    
    signs = sorted(list(set(s for s in signs_full if s != 0)))
    m = len(signs)

    if m < 3:
        print(-1)
        return

    for i in range(63):
        count = 0
        for sign in signs:
            if (sign >> i) & 1:
                count += 1
        if count >= 3:
            print(3)
            return

    adj = [[] for _ in range(m + 63)]
    for i in range(m):
        for j in range(63):
            if (signs[i] >> j) & 1:
                adj[i].append(m + j)
                adj[m + j].append(i)

    min_len = float('inf')

    # Start BFS from bit-nodes, which are fewer
    for i in range(63):
        start_node = m + i
        if not adj[start_node]:
            continue

        q = deque([start_node])
        dist = [-1] * (m + 63)
        parent = [-1] * (m + 63)
        dist[start_node] = 0

        while q:
            u = q.popleft()
            for v in adj[u]:
                if v == parent[u]:
                    continue
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    parent[v] = u
                    q.append(v)
                else:
                    min_len = min(min_len, dist[u] + dist[v] + 1)
    
    if min_len == float('inf'):
        print(-1)
    else:
        print(min_len // 2)

solve()

算法及复杂度

算法: 图变换 + 广度优先搜索 (BFS)
时间复杂度: $O(N \cdot \log S_{max})$ 。
- $N$ 是星系数量, $S_{max}$ 是签名的最大值 ( $\approx 2^{63}$ )。
- 预处理（去重、去零）需要 $O(N \log N)$ （如果使用排序）或 $O(N)$ （如果使用哈希表）。
- 3-环捷径检查需要遍历所有有效签名和所有比特位，复杂度为 $O(N \cdot \log S_{max})$ 。
- 构建星系-比特位图的邻接表，复杂度为 $O(N \cdot \log S_{max})$ 。
- 从每个比特位节点（常数个，约64个）进行 BFS。每次 BFS 的复杂度为 $O(V' + E')$ ，其中 $V' = N+64$ ， $E' = O(N \cdot \log S_{max})$ 。总 BFS 复杂度为 $O(\log S_{max} \cdot (N + N \cdot \log S_{max}))$ , 近似为 $O(N \cdot (\log S_{max})^2)$ 。
- 主导项是图的构建和 BFS 过程，总复杂度约为 $O(N \cdot \log S_{max})$ 。
空间复杂度: $O(N \cdot \log S_{max})$ 。
- 主要用于存储星系-比特位图的邻接表。