Codeforces Round #580 (Div. 2) D Shortest Cycle（最小环）

今天药忘吃喽~ 2021-10-12 19:24 171阅读 0赞

## 题意：给你n个数，如果每两个数且（and）不为0，可以连无向边，求最小环。 ##

## 分析：最小环可以利用Floyd来搞，n太大，如果n很小就可以直接搞了，考虑把n缩小，因为最小环是3，所有只要某一位的个数大于等于3，那么肯定结果就是3，由容斥原理（鸽巢定理）可知，当非0的个数大于63\*2时，肯定会有一个位的个数大于2，或者直接统计每一位的个数也行，这样就可以把n缩小到100多了，直接跑Floyd就好了。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N=150;
    const int M=1e5+5;
    
    ll n,cnt,ans=1e9,a[M],d[N][N],e[N][N];
    int main() {
    	cin>>n;
    	for(int i=0; i<n; i++) {
            ll x;
    		cin>>x;
    		if(x) a[cnt++] = x;
    	}
    	if(cnt>150) {cout<<"3\n"; return 0;}
    	for(int i=0; i<cnt; i++) for(int j=0; j<cnt; j++) {
    		if(i!=j && a[i]&a[j]) d[i][j] = e[i][j] = 1;
    		else d[i][j] = e[i][j] = 1e9;
    	}
    	for(int k=0; k<cnt; k++) {
    		for(int i=0; i<k; i++)
                for(int j=i+1; j<k; j++)
                    ans = min(ans, e[i][k] + e[k][j] + d[i][j]);
    		for(int i=0; i<cnt; i++) for(int j=0; j<cnt; j++)
    			d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    	}
    	if(ans==1e9) cout<<"-1\n";
    	else cout<<ans<<endl;
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Round #580 (Div. 2)

A题---水题： int a[105],b[105]; int main() { int n1,n2; cin>>n1

桃扇骨/ 2023年08月17日 16:26/ 0 赞/ 84 阅读

相关 Codeforces Round #580 (Div. 2)

Solutions -------------------- A. Choose Two Numbers 题意：给出\\(A,B\\)两个集合，\\(A,B

- 日理万妓/ 2023年06月04日 11:58/ 0 赞/ 9 阅读

相关 @codeforces - 1205B@ Shortest Cycle

目录 @description@ @solution@ @accepted code@ @details@ --------------------

Dear 丶/ 2023年06月01日 13:59/ 0 赞/ 12 阅读

相关 Codeforces Round #721 (Div. 2)

[链接][Link 1] Palindrome Game (easy version思维大意思路 code1 code2 大意给定

旧城等待，/ 2022年10月15日 10:54/ 0 赞/ 195 阅读

相关 Codeforces Round 374 div2

题目链接： [ CodeforcesRound374][CodeforcesRound374] 做了这么久cf了，，c题有时候还是做不起，，真的好菜，，，，

Dear 丶/ 2022年07月16日 03:38/ 0 赞/ 199 阅读

相关 Codeforces Round #402 (Div. 2) （A-D）

[CF \402 div2][CF _402 div2] A题：数学。具体看代码吧。很容易明白的。 include<bits/stdc++.h> usi

客官°小女子只卖身不卖艺/ 2022年07月12日 15:16/ 0 赞/ 202 阅读

相关 Codeforces Round #117 (Div. 2)

A : Battlefield 悲剧看了很长时间的题目T\_\_T, :cry: 不会做结果证明当时的决定也是正确的，全场最难的题官网上的思路 Battl

秒速五厘米/ 2022年04月16日 06:47/ 0 赞/ 274 阅读

相关 Codeforces Round #553 (Div. 2)

A：[http://codeforces.com/contest/1151/problem/A][http_codeforces.com_contest_1151_proble

た入场券/ 2021年11月04日 13:36/ 0 赞/ 283 阅读

相关 Codeforces Round #580 (Div. 2) D Shortest Cycle（最小环）

题意：给你n个数，如果每两个数且（and）不为0，可以连无向边，求最小环。分析：最小环可以利用Floyd来搞，n太大，如果n很小就可以直接搞了，考虑把n缩小，因为最小

今天药忘吃喽~/ 2021年10月12日 19:24/ 0 赞/ 172 阅读

相关 Codeforces Round #573 (Div. 2)

<table> <thead> <tr> <th>Sloved</th> <th align="center">A</th> <th alig

浅浅的花香味﹌/ 2021年09月29日 13:10/ 0 赞/ 293 阅读