B. Shortest Cycle 无向图求最小环

B. Shortest Cycle  无向图求最小环

 

 

题意:
给定 n 个点,每个点有一个权值a[i],如果a[u]&a[v] != 0,那么就可以在(u,v)之间连一条边,求最后图的最小环(环由几个点构成)

 

题解:
逻辑运算 & 是二进制下的运算,题目给的每个权值 a[i] 的范围最大是1018,即二进制下最多64位。
如果64位中有某一位的1的出现数大于 2 了,那么很明显,最小环就是3(该位循环)。
换个说法,在最坏的情况下,给出了 n 个数,其中有超过 128 个不为 0 的数,那么答案一定是3(因为当有128个不为0的数时,64位每一位的个数都是2,只要再随便来个不为0的数,都会出现大于2的位数,构成 3 的环)

所以我们只要考虑不为 0 的数的个数小于130的情况就行了,这个时候 n 就很小了,可以用dfs搜索或者用Flyod求最小环。

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<math.h>
#define ll long long
#define mx 0x3f3f3f3f
using namespace std;
ll way[250][250],dis[250][250],num[250];
ll n,m,ans;
void init()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i!=j&&num[i]&num[j])
                way[i][j]=dis[i][j]=1;
            else
                way[i][j]=dis[i][j]=mx;
        }
    }
}
void floyd()
{
    ans=mx;
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
        {
            for(int j=i+1;j<k;j++)
                ans=min(ans,dis[i][j]+way[i][k]+way[k][j]);//接成环
        }

        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]);
    }
}
int main()
{
    while(~scanf("%lld",&n))
    {
        ll cnt=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&num[i]);
            if(num[i])
                cnt++;
        }
        if(cnt>130)
            printf("3\n");
        else
        {
            init();
            floyd();
            if(ans==mx)
                printf("-1\n");
            else
                printf("%lld\n",ans);
        }
    }
    return 0;
}

 

上一篇:Linux 快捷键记录栏


下一篇:京东联盟开发(13)——获取官方活动推广数据