题解 CF1205B 【Shortest Cycle】

· · 题解

最难受的事情莫过于比赛还剩20min，你锁了题，然后叉了自己。

更好的阅读体验

题意

有 N 个数，如果 A_i \ and \ A_j \neq 0 ，则 (i,j) 有一条边。求最小的环。没有环输出 -1 。

N\le 100000 \ , \ A_i\le 10^{18}

题解

直接连边显然是 N^2 ，考虑对其进行优化。

新建 64 个中转点，如果 A_i 的二进制的第 k 位是 1 ，就把它和第 k 个中转点相连。这样有 N+64 个点，最多 64N 条边。答案为最小环 \div 2 。

但这样其实是有问题的，如下面的数据（我叉我自己）：

3
1 1 3

三个点都连在第 1 个中转点上，它们之间就可以构成环，但如果按照上述方式连边就会得到 -1 。

所以对每一个中转点记录度数 c[k] ，如果 c[k]\geq 3 ，那么答案就是 3 。

然后就可以 \text{dfs} 找环了。记录深度和访问情况，如果找到环当前答案就是 \dfrac{(deep[x]-deep[y])+1}{2} 。

但这样也有问题，如果遇到环套环，就可能会走冤枉路。那么从每个点出发 \text{dfs} 一遍就好了。

什么？你说这是 N^2 的？不，如果所有 c[k] < 3 ，那么最多 128 个点，显然是够的。

Time limit exceeded on test 17（尴尬）

原来还有 0 这个搅屎棍，把它忽略掉就行了。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct Edge {
    ll next,to;
} edge[12800005];
bool vis[100105];
ll cnt,head[100105],n,ans=1e18,pcnt,id,s[100105],deep[100105],c[100105];

inline void add(ll u,ll v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(ll x,ll f,ll dep)
{
    vis[x]=1;
    deep[x]=dep;
    for (ll i=head[x];i;i=edge[i].next)
    {
        ll y=edge[i].to;
        if (y==f) continue;
        if (vis[y])
        {
            ll cur=abs(deep[y]-deep[x])+1; //因为是双向边，所以可能出现负数，取绝对值即可
            if (cur==4) continue; //如果环大小为4，那么在原图中是自环
            ans=min(ans,cur>>1);
        }
        else dfs(y,x,dep+1);
    }
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read(),pcnt+=s[i]>0;
    for (ll i=1;i<=n;i++)
    {
        if (!s[i]) continue; //跳过0
        id++;
        for (ll j=63;~j;j--)
        {
            if (s[i]>>j&1)
            {
                add(id,j+pcnt+1);
                add(j+pcnt+1,id); //连边
                c[j]++;
            }
        }
    }
    n=pcnt;
    for (int i=63;~i;i--)
    {
        if (c[i]>=3)
        {
            ans=3;
            goto output;
        }
    }
    for (ll i=1;i<=n+64;i++)
    {
        memset(vis,0,sizeof(vis));
        memset(deep,0,sizeof(deep));
        dfs(i,0,1);
    }
    if (ans==1e18) ans=-1;
    output:
    cout<<ans;
    return 0;
}