题意
若两个数字AND之后不为零则🔗一条边，求图中是否存在环及最小环。
求解最小环
第一次接触求最小环问题，虽然说图论板题多可是他的板子也是真的多啊。。。
求图中的最小环主要有两种方法。
传统的解决方法(dijkstra)
设置w为原图，dis为最短路图，
任意一个环的权值，我们都可以看成i、j的直接距离加上i、j间不包含边(边i->j)的最短路径（w[ i ][ j ]+dis[ j ][ i ]）。求最短路径我们第一个想到的就是Dijkstra算法。而Dijkstra所求的是一个点到所有点的最短距离。用Dijkstra所求的i、j的最短距离一定是i、j的直接距离(如果i，j连通)，所以我们需要先将i、j的边从图中删除(若i，j不连通，则不用删除)，再用Dijkstra求新图中i、j的最短距离即可。所以我们每次在图中选取一条边，把它从图中删掉．然后对删掉的那条边所对应的2点进行Dijkstra，也就是m次Dijkstra。
floyd求最小环（万能Floyd）
Floyd算法在进行时会不断更新矩阵dist(k)。设dist[k，i，j]表示从结点i到结点j且满足所有中间结点，它们均属于集合{1，2，⋯ ，k}的一条最短路径的权。其中dist[0，i，j ]即为初始状态i到j的直接距离。对于一个给定的赋权有向图， 求出其中权值和最小的一个环。我们可以将任意一个环化成如下形式：
u->k->v ->(x1-> x2-> ⋯ xm1)-> u，其中v ->(x1-> 2-> ⋯ m)-> u是指v到u不经过k的一种路径。注意，u与k、k与v都是直接相连的。在u，k，v确定的情况下，要使环权值最小，即要求括号内为v到u不经过k的最短路径。
现在我们给k加一个限制条件：k为当前环中的序号最大的节点。
则这个经过u，k，v的环的最短路径就是：w[u，k]+w[k，v]+dist[k-1，v，u]。
a的范围是1e18，也就是说二进制下最多60几位。如果存在有一位为1的数的数量大于2，那么最小环的数量就可以直接得到为3。因为这一位为1的几个数都是互相连通的，也就是说这几个数可以组成一个无向完全图，最小环直接就是3了。这样，我们在k变量变化的同时，也就是进行Floyd算法的同时，寻找最大点为k的最小环。
关于题目~🐢
再看，考虑极端情况：如果每一位都刚好只有两个数的时候，就是n=63*2的时候有可能出现。那么如果n > 126呢？是不是就一定会出现上一段的情况了？是的。所以对于n>130【开大点儿保险】，可以直接输出答案为3。
所以还有一个很关键很关键的步骤——把0全部去掉，看剩下的干货的数量和130的关系。
所以至此，我们真正可以用暴力处理的n的范围就在130以内了。
int n,tot;
ll a[MAXN];
ll dis[222][222],w[222][222];
void floyd()
{
ll ans=INF;
for(int k=1;k<=n;++k)
{
for(int i=1;i<k;++i)//此时i,j也应小于k
for(int j=i+1;j<k;++j)
ans=min(ans,dis[i][j]+w[i][k]+w[k][j]);//先更新答案,因为要保证点集是1..k-1
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
if(ans==INF)
printf("-1\n");
else
printf("%lld\n",ans);
}
int main()
{
rd(n);
for(int i=1;i<=n;++i)
{
++tot;
rd(a[tot]);
if(!a[tot]) --tot;
}
if(tot>130)
{
printf("3\n");
return 0;
}
n=tot;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
dis[i][j]=w[i][j]=INF;
for(int i=2;i<=n;++i)
for(int j=1;j<i;++j)
if(a[i]&a[j])
dis[i][j]=dis[j][i]=w[i][j]=w[j][i]=1;
floyd();
return 0;
} 
京公网安备 11010502036488号