CF 1206D - Shortest Cycle Floyd求最小环
2024-10-02 06:10:26
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 ;
}
最新文章
- 关于redis的keys命令的性能问题
- 数据分析之pandas入门
- JS问题汇总
- 【原创】C#玩高频数字彩快3的一点体会
- Rxjava基础
- 【Win10】在应用中使用 SQLite 数据库
- JAX-WS:背后的技术JAXB及传递Map
- 使用Npoi向Excel中插入图片
- Unity3D脚本中文系列教程(三)
- cocos2d-x3.0+Eclipse配置说明
- C#实现插入排序法
- JS拖动技术--- 关于setCapture
- 休息,归类一下CSS初级的东西
- (译)Web是如何工作的(2):客户端-服务器模型,以及Web应用程序的结构
- KaliLinuxNetHunter教程刷入第三方Recovery与开始刷机
- SQL server SELECT 语句的基本结构
- .net 添加api不能访问的问题
- esxi虚拟机克隆后的主机网卡设置
- 第26月第20天 springboot
- 通信——基于Xmpp协议实现的聊天室