Codeforces Round #580 (Div. 2) D

标签： Floyd 二进制拆分

---

题目描述

戳这里

题解

首先对于这种涉及二进制的运算我们容易想到二进制拆分，对于每一位我们开一个$vector$，表示有多少个值这一位为$1$，那么对于$vector[i]$里面的所有值互相都可以连边，即为一个完全图。而题目要求最小环，那么如果$vector.size()>=3$，直接输出$3$即可，否则就建边。
于是问题就转换成求图中最小环（然后YY了一个dfs的假做法卡到自闭）用$Floyd$算法即可求最小环

代码

#include<bits/stdc++.h>
#define N 100010
#define M 1010
#define ll long long
using namespace std;

ll n, bin = 1, maxn, cnt, ans, k, bid;
ll a[N];
int d[M][M], f[M][M];
bool vis[N];
vector<ll> w[M];
map<int, int> m;

int main()
{
    scanf("%I64d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%I64d", &a[i]);
        maxn = max(a[i], maxn);
    }
    while(bin <= maxn) bin <<= 1, cnt ++;
    ll b = 1;
    for(int j = 0; j < cnt; j ++, b *= 2)
        for(int i = 1; i <= n; i ++)
            if(a[i] & b) w[j].push_back(i);
    for(int i = 0; i < cnt; i ++)
        if(w[i].size() > 2) {printf("3"); return 0;}
    memset(d, 0x3f3f3f3f, sizeof(d));
    memset(f, 0x3f3f3f3f, sizeof(f));
    for(int i = 0; i < cnt; i ++)
    {
        if(w[i].size() < 2) continue;
        int u = w[i][0], v = w[i][1];
        if(!m[u]) m[u] = ++ bid;
        if(!m[v]) m[v] = ++ bid;
        d[m[u]][m[v]] = d[m[v]][m[u]] = 1;
        f[m[u]][m[v]] = f[m[v]][m[u]] = 1;
    }
    for(int i = 1; i <= bid; i ++)
        d[i][i] = 0;
    ans = 1061109567;
    for(int k = 1; k <= bid; k ++)
    {
        for(int i = 1; i < k; i ++)
            for(int j = 1; j < k; j ++)
            {
                if(i == j) continue;
                ans = min(ans, (ll)f[i][k] + f[k][j] + d[i][j]);
            }
        for(int i = 1; i <= bid; i ++)
            for(int j = 1; j <= bid; j ++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }
    if(ans == 1061109567) printf("-1\n");
    else printf("%I64d\n", ans);
    return 0;
}

心得

图论的知识好菜啊QAQ