【最小环】CF1205 B

深碍√TFBOYSˉ_ 2024-03-24 18:17 26阅读 0赞

[Problem - 1205B - Codeforces][]

题意：

![ef6ecc610d75496a8a3dfcfd632d972f.png][]

思路：

![034f95e92d954a3d8c2b65413a069ff0.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    constexpr int N = 2e3 + 10;
    constexpr int M = 2e3 + 10;
    constexpr int mod = 998244353;
    constexpr int Inf = 1e18;
    
    int dis[N][N], adj[N][N];
    
    void solve() {
    	int n;
    	std::cin >> n;
    
    	std::vector<int> a(n + 1, 0);
    	for (int i = 1; i <= n; i ++) {
    		std::cin >> a[i];
    		if (a[i] == 0) {
    			n --;
    			i --;
    		}
    	}
    
    	if (n >= 128) {
    		std::cout << 3 << "\n";
    		return;
    	}
    
    	for (int i = 1; i <= n; i ++) {
    		for (int j = 1; j <= n; j ++) {
    			if (i == j) dis[i][j] = adj[i][j] = 0;
    			else dis[i][j] = adj[i][j] = Inf;
    		}
    	}
    
    	for (int i = 1; i <= n; i ++) {
    		for (int j = 1; j <= n; j ++) {
    			if (((a[i] & a[j]) != 0) && (i != j)) {
    				adj[i][j] = 1;
    				dis[i][j] = 1;
    			}	
    		}
    	}
    
    
    	int ans = Inf;
    	for (int k = 1; k <= n; k ++) {
    		for (int i = 1; i <= n; i ++) {
    			for (int j = 1; j <= n; j ++) {
    				if (i == j || j == k || i == k) continue;
    				ans = std::min(ans, dis[i][j] + adj[i][k] + adj[k][j]); 
    			}
    		}
    		for (int i = 1; i <= n; i ++) {
    			for (int j = 1; j <= n; j ++) {
    				if (i == j || j == k || i == k) continue;
    				dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
    			}
    		}
    	}
    
    	if (ans == Inf) {
    		std::cout << -1 << "\n";
    	}else {
    		std::cout << ans << "\n";
    	}
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        
        int t = 1;
    
        while (t--) {
            solve();
        }
        
        return 0;
    }

[Problem - 1205B - Codeforces]: https://codeforces.com/problemset/problem/1205/B
[ef6ecc610d75496a8a3dfcfd632d972f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/711b00faa3574011abc500593aa22c19.png
[034f95e92d954a3d8c2b65413a069ff0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/e635232da09c44509940a048e2367713.png