[Codeforces 1205B]Shortest Cycle(最小环)
[Codeforces 1205B]Shortest Cycle(最小环)
题面
给出n个正整数\(a_i\),若\(a_i \& a_j \neq 0\)，则连边\((i,j)\)（注意i->j的边和j->i的边看作一条。问连边完图的最小环长度
\(n \leq 10^5,0 \leq a_i \leq 10^{18}\)
分析
我们按位考虑.显然满足第i位为1的所有数两两之间都有边，构成一个完全图.
统计第i位为1的数，如果第i位为1的数超过2个，就直接输出3（这3个构成一个最小环)。如果有2个，就连一条边.注意点的编号要离散化，因为前面可能有很多0，导致满足条件的(i,j)编号很大。
因为要建图的时候，每一位最多建一条边，边数<64,点数<128,floyd求最小环\(O(n^3)\)可以卡过
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f
#define maxv 1000
#define maxn 100000
using namespace std;
typedef long long ll;
int n;
ll a[maxn+5];
vector<int>vis[70];
int cnt=0;
int tp[maxn+5];
ll ans=0;
ll edge[maxv+5][maxv+5];
ll dist[maxv+5][maxv+5];
void floyd(){
for(int k=1;k<=cnt;k++){
for(int i=1;i<k;i++){
for(int j=i+1;j<k;j++){
if(dist[i][j]==INF||edge[i][k]==INF||edge[k][j]==INF) continue;
//防止加法溢出
if(dist[i][j]+edge[i][k]+edge[k][j]<ans){
ans=dist[i][j]+edge[i][k]+edge[k][j];
}
}
}
for(int i=1;i<=cnt;i++){
for(int j=1;j<=cnt;j++){
if(dist[i][j]>dist[i][k]+dist[k][j]){
dist[i][j]=dist[i][k]+dist[k][j];
}
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%I64d",&a[i]);
for(ll i=0;i<64;i++){
for(int j=1;j<=n;j++){
if(a[j]&(1ll<<i)) vis[i].push_back(j);
}
}
for(int i=0;i<64;i++){
if(vis[i].size()>2){
printf("3\n");
return 0;
}
}
for(int i=0;i<64;i++){
if(vis[i].size()==2){
tp[++cnt]=vis[i][0];
tp[++cnt]=vis[i][1];
}
}
sort(tp+1,tp+1+cnt);
cnt=unique(tp+1,tp+1+cnt)-tp-1;
memset(edge,0x3f,sizeof(edge));
memset(dist,0x3f,sizeof(dist));
ans=INF;
for(int i=0;i<64;i++){
if(vis[i].size()==2){
int u=lower_bound(tp+1,tp+1+cnt,vis[i][0])-tp;
int v=lower_bound(tp+1,tp+1+cnt,vis[i][1])-tp;
// printf("%d %d\n",u,v);
edge[u][v]=edge[v][u]=1;
}
}
memcpy(dist,edge,sizeof(edge));
floyd();
if(ans==INF) printf("-1\n");
else printf("%d\n",ans);
}
1、Stack Overflow
2、HTTP的DELETE方法Body传递参数问题解决
3、对ESRI的shp文件的一点理解
4、继承
5、Linux 公网IP和内网IP，Dubbo提供者注册到了内网IP上怎么处理！