最小环-Floyd
floyd求最小环
for(k=;k<=n;k++)
{ for(i=;i<k;i++)
for(j=i+;j<k;j++)
if(d[i][j]+m[i][k]+m[k][j]<min)
min=d[i][j]+m[i][k]+m[k][j];
for(i=;i<=n;i++)
for(j=;j<=n;j++)
if(d[i][k]+d[k][j]<d[i][j])
d[i][j]=d[i][k]+d[k][j];
}
个环至少有 3 个顶点,设某环编号最大的顶点为 L ,在环中直接与之相连的两个顶点编号
分别为 M 和 N (M,N < L),则最大编号为 L 的最小环长度即为 Graph(M,L) + Graph(N,L) +
Dist(M,N) ,其中 Dist(M,N) 表示以 0...L-1 号顶点为中间点时的最短路径,刚好符合 Floyd
算法最外层循环到 k=L 时的情况,则此时对 M 和 N 循环所有编号小于 L 的顶点组合即
可找到最大编号为 L 的最小环。再经过最外层 k 的循环,即可找到整个图的最小环。
1 second
256 megabytes
standard input
standard output
You are given nn integer numbers a1,a2,…,ana1,a2,…,an. Consider graph on nn nodes, in which nodes ii, jj (i≠ji≠j) are connected if and only if, aiaiAND aj≠0aj≠0, where AND denotes the bitwise AND operation.
Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.
The first line contains one integer nn (1≤n≤105)(1≤n≤105) — number of numbers.
The second line contains nn integer numbers a1,a2,…,ana1,a2,…,an (0≤ai≤10180≤ai≤1018).
If the graph doesn't have any cycles, output −1−1. Else output the length of the shortest cycle.
4
3 6 28 9
4
5
5 12 9 16 48
3
4
1 2 4 8
-1
In the first example, the shortest cycle is (9,3,6,28)(9,3,6,28).
In the second example, the shortest cycle is (5,12,9)(5,12,9).
The graph has no cycles in the third example.
分析:对于大于2 * 64个正数的情况直接输出3;其余的情况怼入vector跑floyd求最小环。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + ;
vector<ll> vec;
ll g[][];
ll dis[][];
int num; int floyd()
{
ll res = 1e9;
for (int i = ; i <= num; i++)
for (int j = ; j <= num; j++)
dis[i][j] = g[i][j];
for (int k = ; k <= num; k++)
{
for (int i = ; i < k; i++)
for (int j = i + ; j < k; j++)
res = min(res, dis[i][j] + g[i][k] + g[k][j]);
for (int i = ; i <= num; i++)
for (int j = ; j <= num; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
return res != 1e9 ? res : -;
} int main()
{
int n; cin >> n;
int cnt = ;
ll x; for (int i = ; i <= n; i++)
{
scanf("%lld", &x);
if (x > ) cnt++, vec.push_back(x);
}
if (cnt >= )
{
cout << "" << endl;
return ;
}
num = vec.size();
for (int i = ; i < num; i++)
for (int j = i + ; j < num; j++)
g[i + ][j + ] = g[j + ][i + ] = (vec[i] & vec[j]) ? : inf;
cout << floyd() << endl;
}
最新文章
- RecyclerView如何消除底部的分割线
- 使用git的分支功能实现定制功能摘取与组合的想法
- 在Ubuntu下安装imx6linux系统的交叉编译环境遇到的问题总结
- socket编程里的read和recv函数【转载】
- bin
- Redmine管理项目3-调整用户显示格式
- 五分钟秒懂Java日志组件
- linux 巨页使用测试以及勘误1
- epoll通俗讲解
- python算法&;二分查找法
- Eclipse拷贝动态的web工程修改context root的值
- Workspace in use or cannot be created, choose a different one.错误的解决办法
- VC 预定义宏
- UEditor在asp.netMVC4中的使用,包括上传功能,粘贴表格不显示边框问题
- Linux 下 mysql的基本配置
- 开机或联网时自启动gunicorn
- 【LG4248】[AHOI2013]差异
- GMM实战
- 分享:Windows2008重启后提示系统恢复选项的解决办法
- 20155308 实验四 Android开发基础