CF1206D:Shortest Path 题解

主要思路

刚开始以为是搞\(\log n\)个基底点,然后双向边上面做事情,最后发现找图上最小环的复杂度非常的高。所以 GG。

正解考虑把问题的规模进行缩小:也就是把一些答案预先特判掉。比如说,如果某一个位上有超过三个点连接,那么环的大小就可以被确定为是\(3\),也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。

再考虑剩下的情况。此时,\(n\)已经缩小了很多,所以我们暴力建图,用 Floyd 跑最小环即可。

代码

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

using namespace std;

const int MAX_N = 1e5 + 200;

ll n, cnt[MAX_N], matrix[150][150], dist[150][150], tot, ai[MAX_N];

int main()
{
    scanf("%d", &n);
    for (ll i = 1, tmp; i <= n; i++)
    {
        scanf("%lld", &tmp);
        if (tmp)
            ai[++tot] = tmp;
    }
    if (tot >= 150)
        puts("3"), exit(0);
    for (int i = 1; i <= tot; i++)
        for (int j = 1; j <= tot; j++)
            if ((ai[i] & ai[j]) != 0 && i != j)
                matrix[i][j] = dist[i][j] = 1;
            else
                matrix[i][j] = dist[i][j] = 1e9;

    // graph contructed;
    ll ans = 1e9;
    for (int k = 1; k <= tot; k++)
    {
        for (int i = 1; i <= tot; i++)
            for (int j = i + 1; j <= tot; j++)
                ans = min(ans, dist[i][j] + matrix[i][k] + matrix[k][j]);
        for (int i = 1; i <= tot; i++)
            for (int j = 1; j <= tot; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }
    if (ans >= 1e9)
        puts("-1");
    else
        printf("%d", ans);
    return 0;
}

发表评论

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