给 \(n\) 个点的图，点有点权 \(a_i\) ，两点之间有边当且仅当 \(a_i\ \text{and}\ a_j \not= 0\)，边权为1，求最小环。
按每一位考虑若当前这一位为 1 的点超过了 2 个，那么答案就为 3 。
否则只会连一条边，于是最多只有 \(60\) 条边，枚举每条边删掉，求最短路 (边权为1，bfs) 即可。
#include <iostream> #include <set> #include <queue> #include <cstring> #include <cstdio> #include <fstream> typedef long long LL; typedef unsigned long long uLL; #define SZ(x) ((int)x.size()) #define ALL(x) (x).begin(), (x).end() #define MP(x, y) std::make_pair(x, y) #define DE(x) cerr << x << endl; #define debug(...) fprintf(stderr, __VA_ARGS__) #define GO cerr << "GO" << endl; using namespace std; inline void proc_status() { ifstream t("/proc/self/status"); cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl; } template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; } const int maxN = 1e5 + 2; int n; LL a[maxN]; int dis[maxN]; bool vis[maxN]; int ans(0x3f3f3f3f); vector<int> g[maxN]; set<pair<int, int> > S; void add(int u, int v) { g[u].push_back(v); g[v].push_back(u); } int main() { #ifndef ONLINE_JUDGE freopen("xhc.in", "r", stdin); freopen("xhc.out", "w", stdout); #endif ios::sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 0; i < 62; ++i) { int cnt = 0; for (int j = 1; j <= n; ++j) { if (a[j] >> i & 1) cnt++; } if (cnt >= 3) { cout << 3 << endl; return 0; } if (cnt != 2) continue; int first = 0, second = 0; for (int j = 1; j <= n; ++j) if (a[j] >> i & 1) { if (!first) { first = j; } else { second = j; break; } } S.insert(MP(first, second)); } for (auto p : S) add(p.first, p.second); for (auto p : S) { int s = p.first, t = p.second; memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); vis[s] = 1; queue<int> q; q.push(s); dis[s] = 0; while (q.size()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (u == s and v == t) continue; if (!vis[v]) { q.push(v); vis[v] = 1; dis[v] = dis[u] + 1; } } } if (dis[t] < 0x3f3f3f3f) chkmin(ans, dis[t] + 1); } if (ans < 0x3f3f3f3f) cout << ans << endl; else cout << -1 << endl; return 0; }转载于:https://www.cnblogs.com/cnyali-Tea/p/11439902.html
相关资源：JAVA上百实例源码以及开源项目