B. Shortest Cycle

最小环问题

这个问题题型之前做过一次。但是现在又忘记了，再次记录一下，模板里面也有这个

/*
 *@author spnooyseed
 */
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int g[200][200] , dis[200][200] ;
ll a[N] ;
vector v[N] ;
unordered_map mp ;
int cnt = 0 , n ;
int work(){
  scanf("%d" , &n) ;
  for(int i = 1  ; i <= n ;i ++ )  {
      ll x ; 
      scanf("%lld" , &x) ;
      ll t = x ;
      cnt = -1 ;
      while(t) {
          ++ cnt ;
          if(t & 1) v[cnt].emplace_back(x) ;
          t /= 2 ;
      }
  }
  cnt = 0 ;
  memset(dis , 0x3f , sizeof dis) ;
  memset(g , 0x3f , sizeof g) ;
  for(int i = 0 ;i <= 61 ;i ++ ) {
      if(v[i].size() == 0) continue ;
      if(v[i].size() == 1 && !mp[v[i][0]]) mp[v[i][0]] = ++ cnt ;
      if(v[i].size() == 2) {
          ll x = v[i][0] , y = v[i][1] ;
          if(!mp[x]) mp[x] = ++ cnt;
          if(!mp[y]) mp[y] = ++ cnt ;
          g[mp[x]][mp[y]] = g[mp[y]][mp[x]] = 1 ;
          dis[mp[x]][mp[y]] = dis[mp[y]][mp[x]] = 1 ;
      }
      if(v[i].size() >= 3) {
          puts("3") ;
          return 0 ;
      }
  }
  ll ans = 1e18 ;
  for(int k = 1; k <= cnt ;k ++ ) {
      for(int i = 1; i < k ;i ++ ) {
          for(int j = i + 1 ; j < k ;j ++ ) {
              if(dis[i][j] == INF || g[i][k] == INF || g[k][j] == INF) continue ;
              ans = min(ans , 1ll * dis[i][j] + g[i][k] + g[k][j]) ;
          }
      }
      for(int i = 1; i <= cnt ;i ++ ) 
       for(int j = 1; j <= cnt ;j ++ ) 
        dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]) ;
  }
  if(ans == 1e18) ans = -1 ;
  cout << ans << "\n" ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
*/
最小环CodeForces

相关

Codeforces Round 628 (Div. 2) E. Ehab's REAL Number Theory Problem

Codeforces Round #610 (Div. 2)

Codeforces Global Round 6.E题

Codeforces Round #611 (Div. 3) E题

CF1545X Codeforces Round #732

codeforces和atcoder的思维题目

Codeforces 1373F - Network Coverage（模拟网络流）

CF1481X Codeforces Round #699

CF1485X Codeforces Round #701

Educational Codeforces Round 7 F. The Sum of the k-th Powers 拉格朗日插值法

Codeforces #731 (div3) E. Air Conditioners

Codeforces Round #675

标签