题目大意

给定\(n\)个整数\(a_1,a_2,a_3, \dots ,a_n\)，若\(i \neq j\)且\(a_i \land a_j \neq 0\)，则节点\(i\)和节点\(j\)相连通。求最小环大小。

\(1 \leq n \leq 10^5\)，\(0 \leq a_i \leq 10^{18}\)。

题解

题目中的\(a_i\)都在long long的范围内，即\(a_i \in [0, 2^{64})\)，则根据容斥原理可得，若集合\(\{ a_i | a_i \neq 0 \}\)的大小\(n\)满足\(n > 128\)，一定有节点数为\(3\)的环。

否则，跑一次Floyd求最小环即可。

// luogu-judger-enable-o2

#include <iostream>

#include <cstdio>

#include <cstring>

#define MAX_N (130 + 5)

using namespace std;

int n;

long long a[MAX_N];

int w[MAX_N][MAX_N], dis[MAX_N][MAX_N];

int ans = 2000000000;

int main()

{

    scanf("%d", &n);

    long long tmp;

    for (int i = 1; i <= n; ++i)

    {

        scanf("%lld", &a[i]);

        if (!a[i]) --i, --n;

        if (i > 128) return printf("3"), 0;

    }

    for (int i = 1; i <= n; ++i)

    {

        for (int j = 1; j <= n; ++j)

        {

            if (i != j && (a[i] & a[j])) w[i][j] = 1;

            else w[i][j] = 100000000;

        }

    }

    memcpy(dis, w, sizeof w);

    for (int k = 1; k <= n; ++k)

    {

        for (int i = 1; i <= n; ++i)

        {

            for (int j = 1; j <= n; ++j)

            {

                if (i == k || i == j || j == k) continue;

                ans = min(ans, dis[i][j] + w[i][k] + w[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]);

            }

        }

    }

    if (ans > n) printf("-1");

    else printf("%d", ans);

    return 0;

}

巴特西

【题解】Shortest Cycle

题目大意

题解

最新文章

热门文章