图论3
Hhy140516
·
·
个人记录
floyd 进阶
用处1
直接求解多源最短路的长度（负边权，正边权）
用处2
判断任意两点的连通关系
这个还可以用 bfs 来做主要是看题目的数据范围
bfs$ 时间复杂度 $O(n \cdot m)
floyd$ 时间复杂度 $O(n^3)
传递思路
x>y$ 且 $y>z
知道这些后，可以得到更多关系
x>y$ 且 $y>z$ ，说明 $x>z
时间复杂度
O(n^3)
模版
void floyd()
{
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
for( int k = 1 ; k <= n ; k++ )
{
dis[j][k] |= (dis[j][i] & dis[i][k]) ;//括号里的必须同时满足，所以是&。前面部分只需满足一个，所以是|
}
}
}
}
关于内存单位
$1byte=8bit
bitset 容器
## 用处
创建多个二进制位
## 优点
1. 存储容量是 $bool$ 的 $\frac{1}{8}$ ， $int$ 的 $\frac{1}{32}
- 多个位的位运算 bitset 更优
缺点
单个位的二进制位运算较慢
定义
bitset<200>bs ;//创建一个200位的二进制
bitset<200>as ;//创建一个200位的二进制
创建了200位，25个字节， \approx 7 个 int ， =25 个 bool
原理
通过维护 0 和 1 的数量，减少 bool 的内存占用，时间也会相应的减少
注意
## 操作
```cpp
//支持各类位运算
bs | as ;
bs << 1 ; //也会向int一样，自动溢出
//自带函数
bs.count() ; //bs串中1的个数
bs.size() ; //bs串的长度
bs.any() ; //是否有1
bs.set() ; //全改为1（可输出，输出的是现在的bs串）
bs.reset() ; //全改为0（可输出，输出的是现在的bs串）
(~bs) ; //每位取反
```
# 例题
## $floyd$ 进阶模块
### [B3611 【模板】传递闭包](https://www.luogu.com.cn/problem/B3611)
#### 题意
模板题，题意简单，无需解释
#### 分析
模板题，容易理解，无需分析
#### 注意
这题**没有**坑
#### 代码
```cpp
#include<bits/stdc++.h>
using namespace std ;
bool dis[105][105] ;// floyd 数组
int n ;
void floyd()
{
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
for( int k = 1 ; k <= n ; k++ )
{
dis[j][k] |= (dis[j][i] & dis[i][k]) ;
}
}
}
}
int main()
{
cin >> n ;
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
cin >> dis[i][j] ;
}
}
floyd() ;
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
cout << dis[i][j] << " " ;
}
cout << "\n" ;
}
return 0 ;
}
```
### [P2881 [USACO07MAR] Ranking the Cows G](https://www.luogu.com.cn/problem/P2881)
#### 题意
有 $n$ 个奶牛， $m$ 个相对关系。其中 $m$ 个相对关系包含 $x$ 和 $y$ ，表示 $x$ 的产奶量比 $y$ 的产奶量大
#### 分析
和上题差不多用，就是统计时不一样
我们知道，要全都知道关系，需要知道每个的关系，就是说需要有 $n \times (n-1) \div 2$ 条边，所以答案就是 $n \times (n-1) \div 2$ 条边 $-$ 给出的矩阵中 $1$ 的个数
#### 注意
这题**没有**坑
#### 代码
```cpp
#include<bits/stdc++.h>
using namespace std ;
bool dis[1005][1005] ;
int n , m ;
void floyd()
{
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
for( int k = 1 ; k <= n ; k++ )
{
dis[j][k] |= (dis[j][i] & dis[i][k]) ;
}
}
}
}
int main()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int x , y ;
cin >> x >> y ;
dis[x][y] = 1 ;//这个点来过
}
floyd() ;
int cnt = n * (n - 1) / 2 ;//有这么多条边
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
cnt -= dis[i][j] ;//减掉1
}
}
cout << cnt ;
return 0 ;
}
```
#### $bitset$ 优化
你会发现前面的代码的时间很不乐观，不信，看[link](https://www.luogu.com.cn/record/173229131)
怎么优化呢？
可以用前面说到的 $bitset$ 容器，前面也说到了，他比 $bool$ 快 $8$ 倍
所以改完后：
```cpp
#include<bits/stdc++.h>
using namespace std ;
bitset<1005> dis[1005] ;
int n , m ;
void floyd()
{
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
for( int k = 1 ; k <= n ; k++ )
{
dis[j][k] = dis[j][k] | (dis[j][i] & dis[i][k]) ;
}
}
}
}
int main()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int x , y ;
cin >> x >> y ;
dis[x][y] = 1 ;
}
floyd() ;
int cnt = n * (n - 1) / 2 ;
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
cnt -= dis[i][j] ;
}
}
cout << cnt ;
return 0 ;
}
```
自信评测！
。。。[link](luogu.com.cn/record/173229732)
你知道为什么说“单个二进制位运算较慢了吧”
继续修改：
```cpp
#include<bits/stdc++.h>
using namespace std ;
bitset<1005> dis[1005] ;
int n , m ;
void floyd()
{
for( int i = 1 ; i <= n ; i++ )
{
for( int j = 1 ; j <= n ; j++ )
{
if(dis[j][i])
{
dis[j] = dis[j] | dis[i] ;
}
}
}
}
int main()
{
cin >> n >> m ;
for( int i = 1 ; i <= m ; i++ )
{
int x , y ;
cin >> x >> y ;
dis[x][y] = 1 ;
}
floyd() ;
int cnt = n * (n - 1) / 2 ;
for( int i = 1 ; i <= n ; i++ )
{
cnt -= dis[i].count() ;
}
cout << cnt ;
return 0 ;
}
```
AC！
[link](https://www.luogu.com.cn/record/173230054)
对比时间： $2.51s:57ms$ ，只想说句 $6