CF-1206D Shortest Cycle 题解

题目大意

给你n个数，如果两个数之间进行与运算的结果不为0，即ai&aj≠0，则说明两点之间有一条无向边。问最小环的权值，如果不存在则输出-1。

解题思路

（比赛的时候看到这个题目完全是懵的。。直接跳了

学长简直是魔鬼啊。。又考了一个我不会的。

自闭ing。。

也好，又学了点新知识。

首先用Floyd是可以求最小环的，但是n的范围为1e5，不可能就这么简单的用FLoyd。

（其实之前完全不知道Floyd可以求最小环。。

a的范围为1e18，也就是说最多二进制60位。

由题意可得，ai&aj≠0就可以确定一条无向边，所以对于非0点来说，只要有一位同时存在三个1，那么那三个点就必然成环。即n>(60+60)，就必定最小环是3。

如果n<120，就可以直接建图，用Floyd求最小环。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5,INF = 1e8;
long long a[N];
int Map[200][200], dis[200][200];

int main() {
	int n,cnt = 0 ;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		long long m;
		cin >> m;
		if (m)	a[cnt++] = m;
	}
	if (cnt > 120) {
		cout << 3 << endl;
		return 0;
	}
	for (int i = 0; i < cnt; i++) {//初始化
		for (int j = 0; j < cnt; j++)
			Map[i][j] = dis[i][j] = INF;
		Map[i][i] = dis[i][i] = 0;
	}
	for (int i = 0; i < cnt; i++)
		for (int j = i + 1; j < cnt; j++)
			if ((a[i] & a[j]) != 0)
				Map[i][j] = Map[j][i] = dis[j][i] = dis[i][j] = 1;//建图
	int m = INF;
	for (int k = 0; k < cnt; k++) {
		for (int i = 0; i < k; i++) {//求最小环
			for (int j = i+1; j < k; j++) {
				m = min(m, Map[i][k] + Map[k][j] + dis[i][j]);
			}
		}
		for (int i = 0; i < cnt; i++) {//正常的Floyd
			for (int j = 0; j < cnt; j++) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	if (m == INF)	cout << -1;
	else cout << m;
	cout << endl;
}