并不对劲的复健训练-CF1205B Shortest Cycle

绝地灬酷狼 2023-08-17 16:46 33阅读 0赞

##### 题目大意 #####

有\\(n\\)(\\(n\\leq 10^5\\))个数\\(a\_1,...,a\_n\\)（\\(a\\leq 10^\{18\}\\)）。有一个图用这个方法生成：若\\(a\_i\\)按位与\\(a\_j\\)不为0，则在\\(a\_i,a\_j\\)间连一条无向边。求这个图的最小环，若无环输出-1。

##### 题解 #####

首先发现当有\\(i,j,k\\in\[1,n\]\\)满足\\(a\_i,a\_j,a\_k\\)在同一二进制位上为1时，最小环一定为3。  
排除掉这种情况后，发现同一二进制位上为1的至多只有两个数，这两个数之间一定连边。  
因为\\(a\\leq10^\{18\}\\)所以只有\\(2^0,...,2^\{60\}\\)这61个二进制位可能会连边，至多涉及122个点。  
只保留边涉及的点，就可以用邻接矩阵存这个图。  
在这个图上求最小环，就可以枚举每条边求删掉该边后起点到终点的最短路+1。

##### 代码 #####

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<ctime>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define view(u,k) for(int k=fir[u];~k;k=nxt[k])
    #define LL long long
    #define maxn 100007
    using namespace std;
    LL read()
    {
        LL x=0,f=1;char ch=getchar();
        while(!isdigit(ch)&&ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
        return x*f;
    }
    void write(int x)
    {
        if(x==0){putchar('0'),putchar('\n');return;}
        int f=0;char ch[20];
        if(x<0)putchar('-'),x=-x;
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
        return;
    }
    int n,to[65][2],num[65],rd[127][127],cnt,vis[maxn],inf[5],e[65][2],cnteg;
    int dis[127],ans,q[127],hd,tl;
    LL a[maxn];
    int main()
    {
        n=read();
        rep(i,1,n)a[i]=read();
        rep(i,0,62)
        {
            rep(j,1,n)if(a[j]&(1ll<<i))
            {
                if(num[i]==2){puts("3");return 0;}
                to[i][num[i]]=j,num[i]++;
            }
        }
        memset(inf,0x7f,sizeof(inf)),ans=inf[0];
        rep(i,0,62)if(num[i]==2)
        {
            if(!vis[to[i][0]])vis[to[i][0]]=++cnt;
            if(!vis[to[i][1]])vis[to[i][1]]=++cnt;
            if(!rd[vis[to[i][0]]][vis[to[i][1]]])
            rd[vis[to[i][0]]][vis[to[i][1]]]=rd[vis[to[i][1]]][vis[to[i][0]]]=1,
            cnteg++,e[cnteg][0]=vis[to[i][0]],e[cnteg][1]=vis[to[i][1]];
        }
        rep(i,1,cnteg)
        {
            rd[e[i][0]][e[i][1]]=rd[e[i][1]][e[i][0]]=0;
            rep(j,1,cnt)dis[j]=inf[0];
            dis[e[i][0]]=0,hd=1,q[tl=1]=e[i][0];
            while(hd<=tl)
            {
                int u=q[hd++];
                rep(j,1,cnt)if(rd[u][j]&&dis[j]==inf[0])
                {
                    dis[j]=dis[u]+1;
                    if(j==e[i][1])break;
                    q[++tl]=j;
                }
                if(dis[e[i][1]]!=inf[0])break;
            }
            if(dis[e[i][1]]!=inf[0])ans=min(dis[e[i][1]]+1,ans);
            rd[e[i][0]][e[i][1]]=rd[e[i][1]][e[i][0]]=1;
        }
        if(ans==inf[0])write(-1);
        else write(ans);
        return 0;
    }

转载于:https://www.cnblogs.com/xzyf/p/11584988.html