建站ABC支持网站备份/网站怎么做谷歌推广

问题：

给你n个值 如果相与$(&)$不为0 则建边 求最小环

解：

安利一波同学写的关于环的博客：https://blog.csdn.net/PHenning/article/details/99713164

首先这道题求最小环 我们可以想到 假若有一个二进制位上 有三个1 那么最短的环长度一定是3

否则建立边  共120多个边

这里谈到求最小环的问题

话说某位巨佬跟我说可以用DFS搜索环  但是这种情况因为是深度优先搜索 会忽略掉环 求不出最小环

这里谈到$floyd$求最小环  证明就是令$k$ 为环上最大 的点 找不经过$k$ 也就是$<k $的点的最短路  注意初始化

$g[i][j]$表示原来的连边情况  $dis[i][j]$ 就是两点间  的距离

code:

memcpy(dis,g,sizeof(dis));for(int k=1;k<=200;k++){for(int i=1;i<k-1;i++)for(int j=i+1;j<=k-1;j++) ans=min(ans,g[i][k]+g[k][j]+dis[i][j]);for(int i=1;i<=200;i++)for(int j=1;j<=200;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}

 #include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
long long a[maxn];
int n,Next[1500],End[1500],Last[maxn],tot,fa[maxn],Dep[maxn],ans=maxn;
int g[1000][1000],dis[1000][1000];
int m;
int ccc=0;
int mmm[2000000]; 
inline void link(int a,int b)
{
Next[++tot]=Last[a];Last[a]=tot;End[tot]=b;
}
bool book[maxn];
void dfs()
{memcpy(dis,g,sizeof(dis));for(int k=1;k<=200;k++){for(int i=1;i<k-1;i++)for(int j=i+1;j<=k-1;j++) ans=min(ans,g[i][k]+g[k][j]+dis[i][j]);for(int i=1;i<=200;i++)for(int j=1;j<=200;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}
}
int main()
{//freopen("data.in","r",stdin); cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=200;i++)for(int j=1;j<=200;j++) g[i][j]=1000000;for(int i=0;i<=60;i++){int cnt=0,A=0,B=0;for(int j=1;j<=n;j++)if((a[j]>>i)&1){if(!A){A=j;if(!mmm[A]) mmm[A]=++ccc;A=mmm[A];}else {B=j;if(!mmm[B]) mmm[B]=++ccc;B=mmm[B];}cnt++;}if(cnt>=3){cout<<3;return 0;}if(cnt==2&&A&&B)g[A][B]=1,g[B][A]=1;}dfs();if(ans==maxn)cout<<-1;else cout<<ans;
}