星际虫洞网络

题目分析

给定 个星系，每个星系有一个"空间量子签名"（非负整数）。两个星系之间能建立虫洞的条件是它们签名的按位与不为零。要求找出最短的航行回路（至少包含 3 个星系），回路长度为虫洞数量。若不存在回路则输出 -1。

思路

本题本质上是在一个按位与图上求最小环（Girth）。

关键观察：利用比特分组降低规模

两个节点有边，当且仅当它们的签名共享至少一个公共比特位。换一个角度看：对于每个比特位 ，所有签名中第 位为 1 的节点两两之间都有边，构成一个团（clique）。

由此可以得到两个重要推论：

1. 快速判三角形：如果某个比特位 对应的节点数 ，那么这三个节点两两相连，直接构成三角形，答案为 3。

1. 节点数大幅缩减：若所有比特位对应的节点数都 ，那么参与构边的"活跃节点"最多只有 个（对于 64 位整数）。在这个规模上可以用经典 BFS 求最小环。

算法流程

1. 遍历所有节点，按比特位分组。若任一比特位有 个节点，直接输出 3。
2. 否则，收集所有签名非零且至少有一条边的节点（最多 128 个）。
3. 在这些节点间暴力建图（两两检查按位与是否非零）。
4. 对每个节点做 BFS，利用经典方法检测最小环：当 BFS 遇到一条非树边 （ 已访问且 不是 的父节点），则找到一个长度为 的环。
5. 取所有环的最小值。若无环输出 -1。

复杂度分析

• 比特分组：
• 建图与 BFS：节点数 ，
• 总时间复杂度：，其中
• 空间复杂度：

代码

C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    vector<long long> a(n);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);

    vector<vector<int>> bit_nodes(64);
    for(int i=0;i<n;i++){
        if(a[i]==0) continue;
        for(int b=0;b<64;b++){
            if((a[i]>>b)&1){
                bit_nodes[b].push_back(i);
            }
        }
    }

    for(int b=0;b<64;b++){
        if((int)bit_nodes[b].size()>=3){
            printf("3\n");
            return 0;
        }
    }

    set<int> active_set;
    for(int b=0;b<64;b++)
        for(int v:bit_nodes[b]) active_set.insert(v);
    vector<int> nodes(active_set.begin(), active_set.end());
    int m = nodes.size();
    if(m==0){ printf("-1\n"); return 0; }

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

    int ans=INT_MAX;
    for(int s=0;s<m;s++){
        vector<int> dist(m,-1);
        vector<int> par(m,-1);
        queue<int> q;
        dist[s]=0;
        q.push(s);
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int v:adj[u]){
                if(dist[v]==-1){
                    dist[v]=dist[u]+1;
                    par[v]=u;
                    q.push(v);
                } else if(par[u]!=v){
                    ans=min(ans,dist[u]+dist[v]+1);
                }
            }
        }
    }
    printf("%d\n",ans==INT_MAX?-1:ans);
    return 0;
}

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();

        List<List<Integer>> bitNodes = new ArrayList<>();
        for (int b = 0; b < 64; b++) bitNodes.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            if (a[i] == 0) continue;
            for (int b = 0; b < 64; b++)
                if (((a[i] >> b) & 1) != 0)
                    bitNodes.get(b).add(i);
        }

        for (int b = 0; b < 64; b++) {
            if (bitNodes.get(b).size() >= 3) {
                System.out.println(3);
                return;
            }
        }

        Set<Integer> activeSet = new TreeSet<>();
        for (int b = 0; b < 64; b++)
            for (int v : bitNodes.get(b)) activeSet.add(v);
        List<Integer> nodes = new ArrayList<>(activeSet);
        int m = nodes.size();
        if (m == 0) { System.out.println(-1); return; }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < m; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++)
            for (int j = i + 1; j < m; j++)
                if ((a[nodes.get(i)] & a[nodes.get(j)]) != 0) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }

        int ans = Integer.MAX_VALUE;
        for (int s = 0; s < m; s++) {
            int[] dist = new int[m];
            int[] par = new int[m];
            Arrays.fill(dist, -1);
            Arrays.fill(par, -1);
            dist[s] = 0;
            Queue<Integer> q = new LinkedList<>();
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        par[v] = u;
                        q.add(v);
                    } else if (par[u] != v) {
                        ans = Math.min(ans, dist[u] + dist[v] + 1);
                    }
                }
            }
        }
        System.out.println(ans == Integer.MAX_VALUE ? -1 : ans);
    }
}

Python

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(data[i+1]) for i in range(n)]

    bit_nodes = [[] for _ in range(64)]
    for i in range(n):
        if a[i] == 0:
            continue
        for b in range(64):
            if (a[i] >> b) & 1:
                bit_nodes[b].append(i)

    for b in range(64):
        if len(bit_nodes[b]) >= 3:
            print(3)
            return

    active = set()
    for b in range(64):
        for v in bit_nodes[b]:
            active.add(v)
    nodes = sorted(active)
    m = len(nodes)
    if m == 0:
        print(-1)
        return

    adj = [[] for _ in range(m)]
    for i in range(m):
        for j in range(i + 1, m):
            if a[nodes[i]] & a[nodes[j]]:
                adj[i].append(j)
                adj[j].append(i)

    ans = float('inf')
    for s in range(m):
        dist = [-1] * m
        par = [-1] * m
        dist[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    par[v] = u
                    q.append(v)
                elif par[u] != v:
                    ans = min(ans, dist[u] + dist[v] + 1)
    print(-1 if ans == float('inf') else ans)

main()

JavaScript

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(/\s+/).map(BigInt);

    const bitNodes = Array.from({length: 64}, () => []);
    for (let i = 0; i < n; i++) {
        if (a[i] === 0n) continue;
        for (let b = 0; b < 64; b++)
            if ((a[i] >> BigInt(b)) & 1n)
                bitNodes[b].push(i);
    }

    for (let b = 0; b < 64; b++) {
        if (bitNodes[b].length >= 3) {
            console.log(3);
            return;
        }
    }

    const activeSet = new Set();
    for (let b = 0; b < 64; b++)
        for (const v of bitNodes[b]) activeSet.add(v);
    const nodes = Array.from(activeSet).sort((x, y) => x - y);
    const m = nodes.length;
    if (m === 0) { console.log(-1); return; }

    const adj = Array.from({length: m}, () => []);
    for (let i = 0; i < m; i++)
        for (let j = i + 1; j < m; j++)
            if (a[nodes[i]] & a[nodes[j]]) {
                adj[i].push(j);
                adj[j].push(i);
            }

    let ans = Infinity;
    for (let s = 0; s < m; s++) {
        const dist = new Array(m).fill(-1);
        const par = new Array(m).fill(-1);
        dist[s] = 0;
        const q = [s];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            for (const v of adj[u]) {
                if (dist[v] === -1) {
                    dist[v] = dist[u] + 1;
                    par[v] = u;
                    q.push(v);
                } else if (par[u] !== v) {
                    ans = Math.min(ans, dist[u] + dist[v] + 1);
                }
            }
        }
    }
    console.log(ans === Infinity ? -1 : ans);
});