codeforces #580(div.2) Shortest Cycle(floyd最小环)

原题连接:http://codeforces.com/contest/1206/problem/D

参考博客:https://blog.csdn.net/weixin_43847416/article/details/99964140

根本没看懂题,看了这位大佬博客后,豁然开朗。题目给的每个权值 a[i] 的范围最大是1e18,二进制下最多64位。
如果64位中有某一位的1的出现数大于 2 了,那么很明显,最小环就是3(该位循环)。
换个说法,在最坏的情况下,给出了 n 个数,其中有超过 128 个不为 0的数,那么答案一定是3(因为当有128个不为0的数时,64位每一位的个数都是2,只要再随便来个不为0的数,都会出现大于2的位数,构成 3 的环)

所以我们只要考虑不为 0 的数的个数小于等于128的情况就行了,这个时候 n 就很小了,我是用的floyd求最小环

关于floyd求最小环,可以看一下这位大佬的博客:https://www.cnblogs.com/DF-yimeng/p/8858184.html

代码:

#include <bits/stdc++.h>
using namespace std;
long long a[100010];
long long e[200][200];
long long c[200][200];
long long inf=999999999;
long long minf=99999999999999999;
int main()
{
    long long n;
    long long op=0,r;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {scanf("%lld",&r);
    if(r!=0)
    {a[op]=r;
    op++;}}
    if(op>128)
    {cout<<"3"<<endl;}
    else
    {
        n=op;
        for(int i=0;i<n-1;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(a[i]&a[j])
                {e[i][j]=e[j][i]=1;
                c[i][j]=c[j][i]=1;}
                else
                {e[i][j]=e[j][i]=999999999;
                c[i][j]=c[j][i]=inf;}
            }
        }
        long long ans=minf;
        for(int k=0;k<n;k++)
        {
            for(int i=0;i<k;i++)
            {
                for(int j=i+1;j<k;j++)
                {
                    long long tmp=e[i][k]+e[k][j]+c[i][j];
                    if(tmp<ans)
                    {ans=tmp;}
                }
            }
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(c[i][k]+c[k][j]<c[i][j])
                    {c[i][j]=c[i][k]+c[k][j];}
                }
            }
        }
        if(ans==minf||ans>inf)
        {printf("-1\n");}
        else
        {printf("%lld\n",ans);}
    }
    return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注