CF 1206D - Shortest Cycle Floyd求最小环

时间：2023-03-10 06:05:48
CF 1206D - Shortest Cycle Floyd求最小环

Shortest Cycle

题意

有n(n <= 100000)个数字，两个数字间取&运算结果大于0的话连一条边。问图中的最小环。

思路

可以发现当非0数的个数很大，比如大于200时，一定存在长度为3的环。

如果小于200, 我们就用到了Floyd求最小环的技巧。

#include <algorithm>

#include  <iterator>

#include  <iostream>

#include   <cstring>

#include   <cstdlib>

#include   <iomanip>

#include    <bitset>

#include    <cctype>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <stack>

#include     <cmath>

#include     <queue>

#include      <list>

#include       <map>

#include       <set>

#include   <cassert>

#include <unordered_map>

// #include<bits/extc++.h>

// using namespace __gnu_pbds;

using namespace std;

#define pb push_back

#define fi first

#define se second

#define debug(x) cerr<<#x << " := " << x << endl;

#define bug cerr<<"-----------------------"<<endl;

#define FOR(a, b, c) for(int a = b; a <= c; ++ a) 

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;

const ll inff = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

template<typename T>

inline T read(T&x){

    x=;int f=;char ch=getchar();

    while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();

    while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();

    return x=f?-x:x;

}

/**********showtime************/

            const int maxn = 2e5+;

            ll a[maxn];

            int cnt[];

            ll ans;

            ll dp[][], g[][];

            vector<ll>b;

int main(){

            int n;

            scanf("%d", &n);

            int cnt = ;

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

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

                if(a[i] == ) cnt++;

                else b.pb(a[i]);

            }

            if(n - cnt > ) puts("");

            else  {

                int n = b.size();

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

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

                        if(i == j) dp[i][j] = ,g[i][j] = ;

                        else dp[i][j] = dp[j][i] = inf, g[i][j] = inf;

                    }

                }

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

                    for(int j=i+; j<n; j++) {

                        if((b[i] & b[j]) > ) {

                            dp[i+][j+] = ;

                            dp[j+][i+] = ;

                            g[i+][j+] = ;

                            g[j+][i+] = ;

                        }

                    }

                }

                ans = inf;

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

                    for(int i=; i<k; i++) {

                        for(int j=i+; j<k; j++) {

                            ans = min(ans, dp[i][j] + g[k][i] + g[k][j]);

                        }

                    }

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

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

                            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

                        }

                    }

                }

                if(ans == inf) puts("-1");

                else printf("%lld\n", ans);

            }

            return ;

}